Function SortBuffer

3rdParty/PKWare/implode.cpp:139–183

Builds the "hash_to_index" table and "pair_hash_offsets" table. Every element of "hash_to_index" will contain lowest index to the "pair_hash_offsets" table, effectively giving offset of the first occurence of the given PAIR_HASH in the input data.

// "pair_hash_offsets" table, effectively giving offset of the first
// occurence of the given PAIR_HASH in the input data.
static void PKWAREAPI SortBuffer(TCmpStruct * pWork, unsigned char * buffer_begin, unsigned char * buffer_end)
{
    unsigned short * phash_to_index;
    unsigned char  * buffer_ptr;
    unsigned short total_sum = 0;
    unsigned long byte_pair_hash;           // Hash value of the byte pair
    unsigned short byte_pair_offs;          // Offset of the byte pair, relative to "work_buff"

    // Zero the entire "phash_to_index" table
    memset(pWork->phash_to_index, 0, sizeof(pWork->phash_to_index));
    
    // Step 1: Count amount of each PAIR_HASH in the input buffer
    // The table will look like this:
    //  offs 0x000: Number of occurences of PAIR_HASH 0
    //  offs 0x001: Number of occurences of PAIR_HASH 1
    //  ...
    //  offs 0x8F7: Number of occurences of PAIR_HASH 0x8F7 (the highest hash value)
    for(buffer_ptr = buffer_begin; buffer_ptr < buffer_end; buffer_ptr++)
        pWork->phash_to_index[BYTE_PAIR_HASH(buffer_ptr)]++;

    // Step 2: Convert the table to the array of PAIR_HASH amounts. 
    // Each element contains count of PAIR_HASHes that is less or equal
    // to element index
    // The table will look like this:
    //  offs 0x000: Number of occurences of PAIR_HASH 0 or lower
    //  offs 0x001: Number of occurences of PAIR_HASH 1 or lower
    //  ...
    //  offs 0x8F7: Number of occurences of PAIR_HASH 0x8F7 or lower
    for(phash_to_index = pWork->phash_to_index; phash_to_index < &pWork->phash_to_index_end; phash_to_index++)
    {
        total_sum = total_sum + phash_to_index[0];
        phash_to_index[0] = total_sum;
    }

    // Step 3: Convert the table to the array of indexes.
    // Now, each element contains index to the first occurence of given PAIR_HASH
    for(buffer_end--; buffer_end >= buffer_begin; buffer_end--)
    {
        byte_pair_hash = BYTE_PAIR_HASH(buffer_end);
        byte_pair_offs = (unsigned short)(buffer_end - pWork->work_buff);

        pWork->phash_to_index[byte_pair_hash]--;
        pWork->phash_offs[pWork->phash_to_index[byte_pair_hash]] = byte_pair_offs;
    }
}

static void PKWAREAPI FlushBuf(TCmpStruct * pWork)
{