compress.c

WinCE5.0部分核心源码

#define out_bits_9(w)              \
     if (bit > 9) {                \
       byte|=(w << (bit-9));       \
       *pbyte++=(UCHAR)(byte >> 8);\
       bit--;                      \
       byte <<= 8;                 \
     } else {                      \
       bit=16; byte |= w;          \
       *pbyte++=(UCHAR)(byte >> 8); *pbyte++=(UCHAR)(byte); byte=0; \
     }


#define out_bits_10(w)             \
     if (bit > 10) {               \
       bit-=10; byte |= (w << bit); *pbyte++ = (UCHAR)(byte >> 8); bit+=8; byte <<=8; \
     } else {                      \
       out_bits_2((w >> 8));       \
       out_bits_8((w & 0xFF));     \
     }

//
// Weird effect - if out_bits_9 used instead of out_bits_8,
// it's faster!  if (bit == 11) is faster than if (bit != 11).
//

#define out_bits_11(w)             \
     if (bit > 11) {               \
        bit-=11; byte |= (w << bit); *pbyte++ = (UCHAR)(byte >> 8); bit+=8; byte <<=8; \
     } else {                      \
        if (bit == 11) {           \
          bit=16; byte |= w;       \
          *pbyte++=(UCHAR)(byte >> 8); *pbyte++=(UCHAR)(byte); byte=0; \
        } else {                   \
          bit=11-bit;              \
          byte|=(w >> bit);        \
          *pbyte++=(UCHAR)(byte >> 8); *pbyte++=(UCHAR)(byte); \
          bit=16-bit;              \
          byte=(w << bit);         \
        }                          \
     }


#define out_bits_12(w)             \
     if (bit > 12) {               \
        bit-=12; byte |= (w << bit); *pbyte++ = (UCHAR)(byte >> 8); bit+=8; byte <<=8; \
     } else {                      \
        out_bits_4((w >> 8));      \
        out_bits_8((w & 0xFF));    \
     }
    
#define out_bits_13(w)             \
     if (bit > 13) {               \
        bit-=13; byte |= (w << bit); *pbyte++ = (UCHAR)(byte >> 8); bit+=8; byte <<=8; \
     } else {                      \
        out_bits_5((w >> 8));      \
        out_bits_8((w & 0xFF));    \
     }

#define out_bits_14(w)             \
     if (bit > 14) {               \
        bit-=14; byte |= (w << bit); *pbyte++ = (UCHAR)(byte >> 8); bit+=8; byte <<=8; \
     } else {                      \
        out_bits_6((w >> 8));      \
        out_bits_8((w & 0xFF));    \
     }


#define out_reserve_4()            \
     bit-=4; bitptr_advance();


/* Starts the given bit pointer */
#define inbit_start(s) pbyte = s; bit = 16; byte=(*pbyte << 8) + *(pbyte+1); pbyte++;
#define inbit_end()      if (bit != 16) pbyte++;    

#define in_bit_next()    if (bit < 9) {          \
                            bit=16;              \
                            byte <<=8;           \
                            byte |= *(++pbyte);  \
                         }


#define in_bit_advance() if (bit < 9) {          \
                            bit+=8;              \
                            byte <<=8;           \
                            byte |= *(++pbyte);  \
                         }

/* Returns non-zero in bitset if the next bit in the stream is a 1. */
#define in_bit()     bit--; bitset = (byte >> bit) & 1; in_bit_next()


#define in_bits_2(w) bit-=2; w = (byte >> bit) & 0x03;\
                     in_bit_advance();

#define in_bits_3(w) bit-=3; w = (byte >> bit) & 0x07;\
                     in_bit_advance();

#define in_bits_4(w) bit-=4; w = (byte >> bit) & 0x0F;\
                     in_bit_advance();

#define in_bits_5(w) bit-=5; w = (byte >> bit) & 0x1F;\
                     in_bit_advance();

#define in_bits_6(w) bit-=6; w = (byte >> bit) & 0x3F;\
                     in_bit_advance();

#define in_bits_7(w) bit-=7; w = (byte >> bit) & 0x7F;\
                     in_bit_advance();

#define in_bits_8(w) bit-=8; w = (byte >> bit) & 0xFF;\
                     bit+=8; byte <<=8; byte |= *(++pbyte);


#define in_bits_9(w) bit-=9; w = (byte >> bit) & 0x1FF;          \
                     bit+=8; byte <<=8; byte |= *(++pbyte);      \
                     in_bit_advance();

#define in_bits_10(w) if (bit > 10) {                            \
                        bit-=10; w = (byte >> bit) & 0x3FF;      \
                        bit+=8; byte <<=8; byte |= *(++pbyte);   \
                      } else {                                   \
                        in_bits_2(bitset);                       \
                        in_bits_8(w);                            \
                        w= w + (bitset << 8);                    \
                      }

#define in_bits_11(w) if (bit > 11) {                            \
                        bit-=11; w = (byte >> bit) & 0x7FF;      \
                        bit+=8; byte <<=8; byte |= *(++pbyte);   \
                      } else {                                   \
                        in_bits_3(bitset);                       \
                        in_bits_8(w);                            \
                        w= w + (bitset << 8);                    \
                      }


#define in_bits_12(w) if (bit > 12) {                            \
                        bit-=12; w = (byte >> bit) & 0xFFF;      \
                        bit+=8; byte <<=8; byte |= *(++pbyte);   \
                      } else {                                   \
                        in_bits_4(bitset);                       \
                        in_bits_8(w);                            \
                        w= w + (bitset << 8);                    \
                      }



#define in_bits_13(w)\
                      if (bit > 13) {                            \
                        bit-=13; w = (byte >> bit) & 0x1FFF;     \
                        bit+=8; byte <<=8; byte |= *(++pbyte);   \
                      } else {                                   \
                        in_bits_5(bitset);                       \
                        in_bits_8(w);                            \
                        w=w + (bitset << 8);                     \
                      }


#define in_bits_14(w)\
                      if (bit > 14) {                            \
                        bit-=14; w = (byte >> bit) & 0x3FFF;     \
                        bit+=8; byte <<=8; byte |= *(++pbyte);   \
                      } else {                                   \
                        in_bits_6(bitset);                       \
                        in_bits_8(w);                            \
                        w=w + (bitset << 8);                     \
                      }



#if 0
#ifdef DEBUG
char
ChPrint(UCHAR b)
{
    if (isprint(b))
        return (char)b;
    else
        return '.';
}
#endif
#endif


//* compress()
//
//  Function:   Main compression function.
//
//  Parameters:
//      IN  CurrentBuffer -> points to NDIS_WAN_PACKET with data to compress
//      OUT CompOutBuffer -> points to NDIS_WAN_PACKET to compress data to
//      IN  CurrentLength -> points to Length of data to compress
//      IN  context -> connection compress context
//
//  Returns:    Nothing
//
//  WARNING:    CODE IS HIGHLY OPTIMIZED FOR TIME ON 386
//
//
USHORT
compress (UCHAR *CurrentBuffer, UCHAR *CompOutBuffer, ULONG *CurrentLength, SendContext *context)
{
    int     bit;
    int     byte;
    int     backptr ;
    int     cbMatch;
    int     hashvalue ;
    UCHAR   *matchptr ;
    UCHAR   *pbyte;
    UCHAR   *historyptr ;
    UCHAR   *currentptr ;
    UCHAR   *endptr ;
    UCHAR   hashchar1;
    UCHAR   hashchar2;
    UCHAR   hashchar3;
    int     literal ;
    USHORT   status=0;   // return flags

#ifdef DEBUG
	// Worst case data expansion that can occur is 12.5%, which would happen
	// when every byte was encoded as a literal, and each byte was >= 0x80,
	// requiring 9 bits per byte.
	//
	// Write over all the output buffer memory to which we should be entitled,
	// to catch cases where the caller does not provide sufficient space to
	// handle the worst case (which would occur only very rarely).

	memset(CompOutBuffer, 0xDD, (*CurrentLength * 9 + 7) / 8);
#endif

    // Will this packet fit at the end of the history buffer?
    //
    if (((context->CurrentIndex + *CurrentLength) >= (HISTORY_MAX - 1 )) ||
        (context->CurrentIndex == 0)) {
        context->CurrentIndex = 0;   // Index into the history
        status |= PACKET_AT_FRONT << 8;
    }

	//
    // Start out the bit pointing output - CompOutBuffer is where the
	// compressed data is written.
    //
    bitptr_init(CompOutBuffer);

    historyptr = context->History + context->CurrentIndex ;

	//
	// Setup the compress data source pointer.
	//
    currentptr = CurrentBuffer;

    endptr = currentptr + *CurrentLength - 1;

    while (currentptr < (endptr-2)) {

        *historyptr++ = hashchar1 = *currentptr++ ;
        hashchar2 = *currentptr ;
        hashchar3 = *(currentptr+1) ;

        // "fast" hash function
        // hashvalue = (int)hashchar1 ^ xorlookup1[hashchar2] ^ xorlookup2[hashchar3];
        // hashvalue = MULTHASH1(hashchar1, hashchar2, hashchar3) ;

        hashvalue = MULTHASH2(hashchar1, hashchar2, hashchar3) ;

        matchptr = context->History  + context->HashTable[hashvalue] ;

        if (matchptr != (historyptr - 1))
            context->HashTable[hashvalue] = historyptr - context->History ;

        if (context->ValidHistory < historyptr)
            context->ValidHistory = historyptr ;

        if (matchptr != context->History &&
            *(matchptr-1) == hashchar1 && *matchptr  == hashchar2 &&
            *(matchptr+1) == hashchar3 && matchptr    != (historyptr - 1) &&
            matchptr      != historyptr  && (matchptr+1)  <= context->ValidHistory) {

            backptr = (historyptr - matchptr) & (HISTORY_SIZE - 1) ;

            *historyptr++ = hashchar2 ;     // copy the other 2 chars
            *historyptr++ = hashchar3 ;     // copy the other 2 chars
            currentptr  +=2 ;
            cbMatch = 3 ;           // length of match
            matchptr    +=2 ; // we have already matched 3

            while ((*matchptr == *currentptr) && (currentptr < endptr) && (matchptr <= context->ValidHistory)) {
                matchptr++ ;
                *historyptr++ = *currentptr++ ;
                cbMatch++ ;
            }

#if 0
#ifdef DEBUG
            DbgPrint("\tCOMP: Location:%d  Char %c, matched length %d, backindex %d\n", (currentptr - context->CompressBuffer), ChPrint(*currentptr), cbMatch, backptr) ;
#endif
#endif

            // First output the backpointer
            //
            if (backptr >= 320) {
                backptr -= 320 ;
                out_bits_8((0xc000 + backptr) >> 8) ;   // 110 + 13 bits
                out_bits_8((backptr)) ;
            } else if (backptr < 64) {          // 1111 + 6 bits
                backptr += 0x3c0 ;
                out_bits_10(backptr);
            } else  {
                backptr += (0xE00 - 64);        // 1110 + 8 bits
                out_bits_12(backptr);
            }

            // output the length of the match encoding
            //
            switch (cbMatch) {
    
                case 3:
                    out_bit_0();    // length of 3 - most common
                    break;
    
                case 4:
                case 5:
                case 6:
                case 7:
                    out_bits_4((cbMatch+4));
                    break;
    
                case 8:
                case 9:
                case 10:
                case 11:
                case 12:
                case 13:
                case 14:
                case 15:
                    out_bits_6((cbMatch+40));
                    break;
    
                case 16:
                case 17:
                case 18:
                case 19:
                case 20:
                case 21:
                case 22:
                case 23:
                case 24:
                case 25:
                case 26:
                case 27:
                case 28:
                case 29:
                case 30:
                case 31:
                    out_bits_8((cbMatch+208));
                    break;
    
                default:
                    if (cbMatch < 64) {
                        out_bits_4(0xF) ;
                        cbMatch -= 32 ;
                        out_bits_6(cbMatch) ;
                    }
                    else if (cbMatch < 128) {
                        out_bits_5(0x1F) ;
                        cbMatch -= 64 ;
                        out_bits_7(cbMatch) ;
                    }
                    else if (cbMatch < 256) {
                        out_bits_6(0x3F) ;
                        cbMatch -= 128 ;
                        out_bits_8(cbMatch) ;
                    }
                    else if (cbMatch < 512) {
                        out_bits_7(0x7F) ;
                        cbMatch -= 256 ;
                        out_bits_9(cbMatch) ;
                    }
                    else if (cbMatch < 1024) {
                        out_bits_8(0xFF) ;
                        cbMatch -= 512 ;
                        out_bits_10(cbMatch) ;
                    }
                    else if (cbMatch < 2048) {
                        out_bits_9(0x1FF) ;
                        cbMatch -= 1024 ;
                        out_bits_11(cbMatch) ;
                    }
                    else if (cbMatch < 4096) {
                        out_bits_10(0x3FF) ;
                        cbMatch -= 2048 ;
                        out_bits_12(cbMatch) ;
                    }
                    else if (cbMatch < 8192) {
                        out_bits_11(0x7FF) ;
                        cbMatch -= 4096 ;
                        out_bits_13(cbMatch) ;
                    }
                    else  {             // 8192 and greater
                        out_bits_12(0xFFF) ;
                        cbMatch -= 8192 ;
                        out_bits_14(cbMatch) ;
                    }
                    break ;
            }

        } else {    // encode a literal

#if 0
#ifdef DEBUG
            DbgPrint("\t COMP:Location %d, <No Match>: '%c'\n", (currentptr - context->CompressBuffer),*currentptr) ;
#endif
#endif
            // temp=literallookup[context->History[i-1]] ;
            literal= hashchar1 ;

            if (literal & 0x80) {
                literal += 0x80;
                out_bits_9(literal) ;
            } else {
                out_bits_8(literal) ;
            }

        }