tools/utils/generators/deflate_generator/huff_codes.cpp
// Upon return, codes[] contains the code lengths,
// and bl_count is the count of the lengths
Upon return, codes[] contains the code lengths,
and bl_count is the count of the lengths
Upon return codes [] contains the code lengths and bl_count is the count of the lengths
void
    create_huff_tree(uint32_t const *histogram,
                     uint32_t hist_size,
                     uint32_t *bl_count,
                     uint32_t *codes,
                     uint32_t max_code_len)
    {
        uint64_t heap[HEAP_SIZE];
        uint64_t *heap_freq = (uint64_t *) (4 + (uint8_t *) &heap[0]);
        uint32_t heap_size;
        uint32_t i, j, k, child, d1, d2, code_len, h_new;
        uint64_t h1, h2;
        uint32_t node_ptr   = NODE_START;
        heap_size = 0;
        for (i    = 0; i < hist_size; i++)
        {
            if (histogram[i] != 0)
                heap[++heap_size] = (((uint64_t) histogram[i]) << FREQ_SHIFT) | i;
        }
        if (heap_size < 2)
        {
            for (i = 1; i <= max_code_len; i++)
            {
                bl_count[i] = 0;
            }
            memset(codes, 0, hist_size * sizeof(*codes));
            if (heap_size == 1)
            {
                codes[(uint32_t) heap[1]] = 1;
                bl_count[1]               = 1;
            }
            return;
        }
        build_heap64(heap, heap_size);
        do
        {
            h1 = heap[1];
            heap[1] = heap[heap_size];
            heap[heap_size--] = 0xFFFFFFFFFFFFFFFFULL;
            heapify64(heap, heap_size, 1);
            h2 = heap[1];
            heap[node_ptr] = (uint32_t) h1;
            heap[node_ptr - 1] = (uint32_t) h2;
            h_new = (h1 + h2) & FREQ_MASK_HI;
            d1 = (uint32_t) h1;
            d2 = (uint32_t) h2;
            if (d1 > d2)
            {
                h2 = h1;
            }
            h_new |= node_ptr | ((h2 + DEPTH_1) & DEPTH_MASK_HI);
            node_ptr -= 2;
            heap[1] = h_new;
            heapify64(heap, heap_size, 1);
        } 
        while (heap_size > 1);
        heap[node_ptr] = (uint32_t) heap[1];
        code_len = 0;
        j        = node_ptr;
        for (i   = node_ptr; i <= NODE_START; i++)
        {
            child = (uint16_t) heap[i];
            if (child > MAX_HEAP)
            {
                d1 = 1 + *(uint32_t *) &(heap_freq[i]);
                *(uint32_t *) &(heap_freq[child])     = d1;
                *(uint32_t *) &(heap_freq[child - 1]) = d1;
            }
            else
            {
                heap[j++] = heap[i];
                d1 = *(uint32_t *) &(heap_freq[i]);
                while (code_len < d1)
                {
                    code_len++;
                    heap[code_len] = 0;
                }
                heap[d1]++;
            }
        }
        if (code_len > max_code_len)
        {
            while (code_len > max_code_len)
            {
                assert(heap[code_len] > 1);
                for (i = max_code_len - 1; i != 0; i--)
                {
                    if (heap[i] != 0)
                        break;
                }
                assert(i != 0);
                heap[i]--;
                heap[i + 1] += 2;
                heap[code_len - 1]++;
                heap[code_len] -= 2;
                if (heap[code_len] == 0)
                    code_len--;
            }
            for (i = 1; i <= code_len; i++)
            {
                bl_count[i] = (uint32_t) (heap[i]);
            }
            for (; i <= max_code_len; i++)
            {
                bl_count[i] = 0;
            }
            for (k = 1; heap[k] == 0; k++)
            {}
            for (i = node_ptr; i < j; i++)
            {
                *(uint32_t *) &(heap_freq[i]) = k;
                heap[k]--;
                for (; heap[k] == 0; k++)
                {}
            }
        }
        else
        {
            for (i = 1; i <= code_len; i++)
            {
                bl_count[i] = (uint32_t) (heap[i]);
            }
            for (; i <= max_code_len; i++)
            {
                bl_count[i] = 0;
            }
        }
        memset(codes, 0, hist_size * sizeof(*codes));
        for (i = node_ptr; i < j; i++)
        {
            h1 = heap[i];
            codes[(uint32_t) h1] = (uint32_t) (h1 >> 32u);
        }
    }
void create_huff_tree ( uint32_t const * histogram , uint32_t hist_size , uint32_t * bl_count , uint32_t * codes , uint32_t max_code_len ) { uint64_t heap [ HEAP_SIZE ] ; uint64_t * heap_freq = ( uint64_t * ) ( 4 + ( uint8_t * ) & heap [ 0 ] ) ; uint32_t heap_size ; uint32_t i , j , k , child , d1 , d2 , code_len , h_new ; uint64_t h1 , h2 ; uint32_t node_ptr = NODE_START ; heap_size = 0 ; for ( i = 0 ; i < hist_size ; i ++ ) { if ( histogram [ i ] != 0 ) heap [ ++ heap_size ] = ( ( ( uint64_t ) histogram [ i ] ) << FREQ_SHIFT ) | i ; } if ( heap_size < 2 ) { for ( i = 1 ; i <= max_code_len ; i ++ ) { bl_count [ i ] = 0 ; } memset ( codes , 0 , hist_size * sizeof ( * codes ) ) ; if ( heap_size == 1 ) { codes [ ( uint32_t ) heap [ 1 ] ] = 1 ; bl_count [ 1 ] = 1 ; } return ; } build_heap64 ( heap , heap_size ) ; do { h1 = heap [ 1 ] ; heap [ 1 ] = heap [ heap_size ] ; heap [ heap_size -- ] = 0xFFFFFFFFFFFFFFFFULL ; heapify64 ( heap , heap_size , 1 ) ; h2 = heap [ 1 ] ; heap [ node_ptr ] = ( uint32_t ) h1 ; heap [ node_ptr - 1 ] = ( uint32_t ) h2 ; h_new = ( h1 + h2 ) & FREQ_MASK_HI ; d1 = ( uint32_t ) h1 ; d2 = ( uint32_t ) h2 ; if ( d1 > d2 ) { h2 = h1 ; } h_new |= node_ptr | ( ( h2 + DEPTH_1 ) & DEPTH_MASK_HI ) ; node_ptr -= 2 ; heap [ 1 ] = h_new ; heapify64 ( heap , heap_size , 1 ) ; } while ( heap_size > 1 ) ; heap [ node_ptr ] = ( uint32_t ) heap [ 1 ] ; code_len = 0 ; j = node_ptr ; for ( i = node_ptr ; i <= NODE_START ; i ++ ) { child = ( uint16_t ) heap [ i ] ; if ( child > MAX_HEAP ) { d1 = 1 + * ( uint32_t * ) & ( heap_freq [ i ] ) ; * ( uint32_t * ) & ( heap_freq [ child ] ) = d1 ; * ( uint32_t * ) & ( heap_freq [ child - 1 ] ) = d1 ; } else { heap [ j ++ ] = heap [ i ] ; d1 = * ( uint32_t * ) & ( heap_freq [ i ] ) ; while ( code_len < d1 ) { code_len ++ ; heap [ code_len ] = 0 ; } heap [ d1 ] ++ ; } } if ( code_len > max_code_len ) { while ( code_len > max_code_len ) { assert ( heap [ code_len ] > 1 ) ; for ( i = max_code_len - 1 ; i != 0 ; i -- ) { if ( heap [ i ] != 0 ) break ; } assert ( i != 0 ) ; heap [ i ] -- ; heap [ i + 1 ] += 2 ; heap [ code_len - 1 ] ++ ; heap [ code_len ] -= 2 ; if ( heap [ code_len ] == 0 ) code_len -- ; } for ( i = 1 ; i <= code_len ; i ++ ) { bl_count [ i ] = ( uint32_t ) ( heap [ i ] ) ; } for ( ; i <= max_code_len ; i ++ ) { bl_count [ i ] = 0 ; } for ( k = 1 ; heap [ k ] == 0 ; k ++ ) { } for ( i = node_ptr ; i < j ; i ++ ) { * ( uint32_t * ) & ( heap_freq [ i ] ) = k ; heap [ k ] -- ; for ( ; heap [ k ] == 0 ; k ++ ) { } } } else { for ( i = 1 ; i <= code_len ; i ++ ) { bl_count [ i ] = ( uint32_t ) ( heap [ i ] ) ; } for ( ; i <= max_code_len ; i ++ ) { bl_count [ i ] = 0 ; } } memset ( codes , 0 , hist_size * sizeof ( * codes ) ) ; for ( i = node_ptr ; i < j ; i ++ ) { h1 = heap [ i ] ; codes [ ( uint32_t ) h1 ] = ( uint32_t ) ( h1 >> 32u ) ; } }
Upon return, codes[] contains the code lengths,
and bl_count is the count of the lengths
Upon return codes [] contains the code lengths and bl_count is the count of the lengths
// handle heaps of 0 or 1 elements //    build_heap_asm(heap, heap_size); //   node_ptr = proc_heap(heap, heap_size, node_ptr); //@    for (i = node_ptr; i <= NODE_START; i++) printf("0x%x\t%016x\n",i,heap[i]); // compute code lengths and code length counts ///    for (i=1; i <= code_len; i++) ///        printf("%d\t%d\n", i, heap[i]); ///        for (i=1; i <= code_len; i++) ///            printf("%d\t%d\n", i, heap[i]); ///    for (i = node_ptr; i<j; i++) ///        printf("%016I64x\n", heap[i]); //    for (i=0; i<hist_size; i++) //        printf("%d\t%d\n", i, codes[i]);