--- /dev/null
+#include "ted5.h"
+#pragma hdrstop
+
+long inlength,outlength;
+
+long counts[256];
+
+unsigned huffbits[256];
+unsigned long huffstring[256];
+
+huffnode nodearray[256]; // 256 nodes is worst case
+
+void CountBytes (unsigned char huge *start, long length);
+void Huffmanize (void);
+void OptimizeNodes (huffnode *table);
+long HuffCompress (unsigned char huge *source, long length,
+ unsigned char huge *dest);
+void HuffExpand (unsigned char huge *source, unsigned char huge *dest,
+ long length,huffnode *hufftable);
+void RLEWExpand (unsigned huge *source, unsigned huge *dest,long length,
+ unsigned rlewtag);
+long RLEWCompress (unsigned huge *source, long length, unsigned huge *dest,
+ unsigned rlewtag);
+
+/*
+=============================================================================
+
+ COMPRESSION SUBS
+
+=============================================================================
+*/
+
+
+/*
+======================
+=
+= CountBytes
+=
+= Adds the bytes in the pointed to area to the counts array
+= If this is the first segment, make sure counts is zerod
+=
+======================
+*/
+
+void CountBytes (unsigned char huge *start, long length)
+{
+ long i;
+
+ while (length--)
+ counts[*start++]++;
+}
+
+/*
+=======================
+=
+= FindLeast
+=
+= Returns the byte with the lowest counts value
+=
+=======================
+*/
+
+int FindLeast (void)
+{
+ int i,least;
+ long low = 0x7fffffff;
+
+ for (i=0;i<256;i++)
+ if (counts[i]<low)
+ {
+ low = counts[i];
+ least = i;
+ }
+
+ return least;
+}
+
+/*========================================================================*/
+
+/*
+==================
+=
+= TraceNode
+=
+= A recursive function that follows all leaves of nodearray and fills in
+= coding tables huffbits and huffstring.
+=
+==================
+*/
+
+void TraceNode (int nodenum,int numbits,unsigned long bitstring)
+{
+ unsigned bit0,bit1;
+
+ bit0 = nodearray[nodenum].bit0;
+ bit1 = nodearray[nodenum].bit1;
+
+ numbits++;
+
+ if (bit0 <256)
+ {
+ huffbits[bit0]=numbits;
+ huffstring[bit0]=bitstring; // just added a zero in front
+ if (huffbits[bit0]>24 && counts[bit0])
+ {
+ puts("Error: Huffman bit string went over 32 bits!");
+ exit(1);
+ }
+ }
+ else
+ TraceNode (bit0-256,numbits,bitstring);
+
+ if (bit1 <256)
+ {
+ huffbits[bit1]=numbits;
+ huffstring[bit1]=bitstring+ (1ul<<(numbits-1)); // add a one in front
+ if (huffbits[bit1]>24 && counts[bit1])
+ {
+ puts("Error: Huffman bit string went over 32 bits!");
+ exit(1);
+ }
+ }
+ else
+ TraceNode (bit1-256,numbits,bitstring+(1ul<<(numbits-1)));
+}
+
+/*
+=======================
+=
+= Huffmanize
+=
+= Takes the counts array and builds a huffman tree at
+= nodearray, then builds a codeing table.
+=
+=======================
+*/
+
+void Huffmanize (void)
+{
+
+//
+// codes are either bytes if <256 or nodearray numbers+256 if >=256
+//
+ unsigned value[256],code0,code1;
+//
+// probablilities are the number of times the code is hit or $ffffffff if
+// it is allready part of a higher node
+//
+ unsigned long prob[256],low,workprob;
+
+ int i,worknode,bitlength;
+ unsigned long bitstring;
+
+
+//
+// all possible leaves start out as bytes
+//
+ for (i=0;i<256;i++)
+ {
+ value[i]=i;
+ prob[i]=counts[i];
+ }
+
+//
+// start selecting the lowest probable leaves for the ends of the tree
+//
+
+ worknode = 0;
+ while (1) // break out of when all codes have been used
+ {
+ //
+ // find the two lowest probability codes
+ //
+
+ code0=0xffff;
+ low = 0x7ffffffff;
+ for (i=0;i<256;i++)
+ if (prob[i]<low)
+ {
+ code0 = i;
+ low = prob[i];
+ }
+
+ code1=0xffff;
+ low = 0x7fffffff;
+ for (i=0;i<256;i++)
+ if (prob[i]<low && i != code0)
+ {
+ code1 = i;
+ low = prob[i];
+ }
+
+ if (code1 == 0xffff)
+ {
+ if (value[code0]<256)
+ Quit("Wierdo huffman error: last code wasn't a node!");
+ if (value[code0]-256 != 254)
+ Quit("Wierdo huffman error: headnode wasn't 254!");
+ break;
+ }
+
+ //
+ // make code0 into a pointer to work
+ // remove code1 (make 0xffffffff prob)
+ //
+ nodearray[worknode].bit0 = value[code0];
+ nodearray[worknode].bit1 = value[code1];
+
+ value[code0] = 256 + worknode;
+ prob[code0] += prob[code1];
+ prob[code1] = 0xffffffff;
+ worknode++;
+ }
+
+//
+// done with tree, now build table recursively
+//
+
+ TraceNode (254,0,0);
+
+}
+
+/*========================================================================*/
+
+
+/*
+===============
+=
+= OptimizeNodes
+=
+= Goes through a huffman table and changes the 256-511 node numbers to the
+= actular address of the node. Must be called before HuffExpand
+=
+===============
+*/
+
+void OptimizeNodes (huffnode *table)
+{
+ huffnode *node;
+ int i;
+
+ node = table;
+
+ for (i=0;i<255;i++)
+ {
+ if (node->bit0 >= 256)
+ node->bit0 = (unsigned)(table+(node->bit0-256));
+ if (node->bit1 >= 256)
+ node->bit1 = (unsigned)(table+(node->bit1-256));
+ node++;
+ }
+}
+
+/*========================================================================*/
+
+#if 0
+/*
+======================
+=
+= HuffCompress
+=
+= The file must be counted with CountBytes and then Huffmanized first
+=
+======================
+*/
+
+long HuffCompress (unsigned char huge *source, long length,
+ unsigned char huge *dest)
+{
+ long outlength;
+ unsigned long string;
+ unsigned biton,bits;
+ unsigned char byte;
+
+ outlength = biton = 0;
+
+ *(long huge *)dest=0; // so bits can be or'd on
+
+ while (length--)
+ {
+ byte = *source++;
+ bits = huffbits[byte];
+ string = huffstring[byte] << biton;
+ *(long huge *)(dest+1)=0; // so bits can be or'd on
+ *(long huge *)dest |= string;
+ biton += bits; // advance this many bits
+ dest+= biton/8;
+ biton&=7; // stay under 8 shifts
+ outlength+=bits;
+ }
+
+ return (outlength+7)/8;
+}
+#endif
+
+
+/*========================================================================*/
+
+/*
+======================
+=
+= HuffExpand
+=
+======================
+*/
+
+void HuffExpand (unsigned char huge *source, unsigned char huge *dest,
+ long length,huffnode *hufftable)
+
+{
+ unsigned bit,byte,node,code;
+ unsigned sourceseg,sourceoff,destseg,destoff,endoff;
+ huffnode *nodeon,*headptr;
+
+ headptr = hufftable+254; // head node is allways node 254
+
+ source++; // normalize
+ source--;
+ dest++;
+ dest--;
+
+ sourceseg = FP_SEG(source);
+ sourceoff = FP_OFF(source);
+ destseg = FP_SEG(dest);
+ destoff = FP_OFF(dest);
+ endoff = destoff+length;
+
+//
+// ds:si source
+// es:di dest
+// ss:bx node pointer
+//
+
+ if (length <0xfff0)
+ {
+
+//--------------------------
+// expand less than 64k of data
+//--------------------------
+
+asm mov bx,[headptr]
+
+asm mov si,[sourceoff]
+asm mov di,[destoff]
+asm mov es,[destseg]
+asm mov ds,[sourceseg]
+asm mov ax,[endoff]
+
+asm mov ch,[si] // load first byte
+asm inc si
+asm mov cl,1
+
+expandshort:
+asm test ch,cl // bit set?
+asm jnz bit1short
+asm mov dx,[ss:bx] // take bit0 path from node
+asm shl cl,1 // advance to next bit position
+asm jc newbyteshort
+asm jnc sourceupshort
+
+bit1short:
+asm mov dx,[ss:bx+2] // take bit1 path
+asm shl cl,1 // advance to next bit position
+asm jnc sourceupshort
+
+newbyteshort:
+asm mov ch,[si] // load next byte
+asm inc si
+asm mov cl,1 // back to first bit
+
+sourceupshort:
+asm or dh,dh // if dx<256 its a byte, else move node
+asm jz storebyteshort
+asm mov bx,dx // next node = (huffnode *)code
+asm jmp expandshort
+
+storebyteshort:
+asm mov [es:di],dl
+asm inc di // write a decopmpressed byte out
+asm mov bx,[headptr] // back to the head node for next bit
+
+asm cmp di,ax // done?
+asm jne expandshort
+ }
+ else
+ {
+
+//--------------------------
+// expand more than 64k of data
+//--------------------------
+
+ length--;
+
+asm mov bx,[headptr]
+asm mov cl,1
+
+asm mov si,[sourceoff]
+asm mov di,[destoff]
+asm mov es,[destseg]
+asm mov ds,[sourceseg]
+
+asm lodsb // load first byte
+
+expand:
+asm test al,cl // bit set?
+asm jnz bit1
+asm mov dx,[ss:bx] // take bit0 path from node
+asm jmp gotcode
+bit1:
+asm mov dx,[ss:bx+2] // take bit1 path
+
+gotcode:
+asm shl cl,1 // advance to next bit position
+asm jnc sourceup
+asm lodsb
+asm cmp si,0x10 // normalize ds:si
+asm jb sinorm
+asm mov cx,ds
+asm inc cx
+asm mov ds,cx
+asm xor si,si
+sinorm:
+asm mov cl,1 // back to first bit
+
+sourceup:
+asm or dh,dh // if dx<256 its a byte, else move node
+asm jz storebyte
+asm mov bx,dx // next node = (huffnode *)code
+asm jmp expand
+
+storebyte:
+asm mov [es:di],dl
+asm inc di // write a decopmpressed byte out
+asm mov bx,[headptr] // back to the head node for next bit
+
+asm cmp di,0x10 // normalize es:di
+asm jb dinorm
+asm mov dx,es
+asm inc dx
+asm mov es,dx
+asm xor di,di
+dinorm:
+
+asm sub [WORD PTR ss:length],1
+asm jnc expand
+asm dec [WORD PTR ss:length+2]
+asm jns expand // when length = ffff ffff, done
+
+ }
+
+asm mov ax,ss
+asm mov ds,ax
+
+}
+
+
+//----------------- replaced by John C. ------------------------------------
+#if 0
+{
+ unsigned bit,byte,node,code;
+ unsigned sourceseg,sourceoff,destseg,destoff,endseg,endoff;
+ huffnode *nodeon,*headptr;
+
+ nodeon = headptr = hufftable+254; // head node is allways node 254
+
+ bit = 1;
+ byte = *source++;
+
+ while (length)
+ {
+ if (byte&bit)
+ code = nodeon->bit1;
+ else
+ code = nodeon->bit0;
+
+ bit<<=1;
+ if (bit==256)
+ {
+ bit=1;
+ byte = *source++;
+ }
+
+ if (code<256)
+ {
+ *dest++=code;
+ nodeon=headptr;
+ length--;
+ }
+ else
+ nodeon = (huffnode *)code;
+ }
+
+
+#if 0
+
+ source++; // normalize
+ source--;
+ dest++;
+ dest--;
+
+ sourceseg = FP_SEG(source);
+ sourceoff = FP_OFF(source);
+ destseg = FP_SEG(dest);
+ destoff = FP_OFF(dest);
+
+ length--;
+//
+// al = source byte
+// cl = bit in source (1,2,4,8,...)
+// dx = code
+//
+// ds:si source
+// es:di dest
+// ss:bx node pointer
+//
+
+asm mov bx,headptr
+asm mov cl,1
+
+asm mov si,sourceoff
+asm mov di,destoff
+asm mov es,destseg
+asm mov ds,sourceseg
+
+asm lodsb // load first byte
+
+expand:
+asm test al,cl // bit set?
+asm jnz bit1
+asm mov dx,ss:bx // take bit0 path from node
+asm jmp gotcode
+bit1:
+asm mov dx,ss:bx+2 // take bit1 path
+
+gotcode:
+asm shl cl,1 // advance to next bit position
+asm jnc sourceup
+asm lodsb
+asm cmp si,0x10 // normalize ds:si
+asm jb sinorm
+asm mov cx,ds
+asm inc cx
+asm mov ds,cx
+asm xor si,si
+sinorm:
+asm mov cl,1 // back to first bit
+
+sourceup:
+asm or dh,dh // if dx<256 its a byte, else move node
+asm jz storebyte
+asm mov bx,dx // next node = (huffnode *)code
+asm jmp expand
+
+storebyte:
+asm mov [es:di],dl
+asm inc di // write a decopmpressed byte out
+asm mov bx,headptr // back to the head node for next bit
+
+asm cmp di,0x10 // normalize es:di
+asm jb dinorm
+asm mov dx,es
+asm inc dx
+asm mov es,dx
+asm xor di,di
+dinorm:
+
+asm sub WORD PTR ss:length,1
+asm jnc expand
+asm dec WORD PTR ss:length+2
+asm jns expand // when length = ffff ffff, done
+
+asm mov ax,ss
+asm mov ds,ax
+
+#endif
+
+}
+#endif
+//---------------------------------------------------------------------------
+
+/*========================================================================*/
+
+/*
+======================
+=
+= RLEWcompress
+=
+======================
+*/
+
+long RLEWCompress (unsigned huge *source, long length, unsigned huge *dest,
+ unsigned rlewtag)
+{
+ long complength;
+ unsigned value,count,i;
+ unsigned huge *start,huge *end;
+
+ start = dest;
+
+ end = source + (length+1)/2;
+
+//
+// compress it
+//
+ do
+ {
+ count = 1;
+ value = *source++;
+ while (*source == value && source<end)
+ {
+ count++;
+ source++;
+ }
+ if (count>3 || value == rlewtag)
+ {
+ //
+ // send a tag / count / value string
+ //
+ *dest++ = rlewtag;
+ *dest++ = count;
+ *dest++ = value;
+ }
+ else
+ {
+ //
+ // send word without compressing
+ //
+ for (i=1;i<=count;i++)
+ *dest++ = value;
+ }
+
+ } while (source<end);
+
+ complength = 2*(dest-start);
+ return complength;
+}
+
+
+
+/*
+======================
+=
+= RLEWexpand
+=
+======================
+*/
+
+void RLEWExpand (unsigned huge *source, unsigned huge *dest,long length,
+ unsigned rlewtag)
+{
+ unsigned value,count,i;
+ unsigned huge *end;
+ unsigned sourceseg,sourceoff,destseg,destoff,endseg,endoff;
+
+
+//
+// expand it
+//
+#if 0
+ do
+ {
+ value = *source++;
+ if (value != rlewtag)
+ //
+ // uncompressed
+ //
+ *dest++=value;
+ else
+ {
+ //
+ // compressed string
+ //
+ count = *source++;
+ value = *source++;
+ for (i=1;i<=count;i++)
+ *dest++ = value;
+ }
+ } while (dest<end);
+#endif
+
+ end = dest + (length)/2;
+ sourceseg = FP_SEG(source);
+ sourceoff = FP_OFF(source);
+ destseg = FP_SEG(dest);
+ destoff = FP_OFF(dest);
+ endseg = FP_SEG(end);
+ endoff = FP_OFF(end);
+
+
+//
+// ax = source value
+// bx = tag value
+// cx = repeat counts
+// dx = scratch
+//
+// NOTE: A repeat count that produces 0xfff0 bytes can blow this!
+//
+
+asm mov bx,rlewtag
+asm mov si,sourceoff
+asm mov di,destoff
+asm mov es,destseg
+asm mov ds,sourceseg
+
+expand:
+asm lodsw
+asm cmp ax,bx
+asm je repeat
+asm stosw
+asm jmp next
+
+repeat:
+asm lodsw
+asm mov cx,ax // repeat count
+asm lodsw // repeat value
+asm rep stosw
+
+next:
+
+asm cmp si,0x10 // normalize ds:si
+asm jb sinorm
+asm mov ax,si
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm mov dx,ds
+asm add dx,ax
+asm mov ds,dx
+asm and si,0xf
+sinorm:
+asm cmp di,0x10 // normalize es:di
+asm jb dinorm
+asm mov ax,di
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm mov dx,es
+asm add dx,ax
+asm mov es,dx
+asm and di,0xf
+dinorm:
+
+asm cmp di,ss:endoff
+asm jne expand
+asm mov ax,es
+asm cmp ax,ss:endseg
+asm jb expand
+
+asm mov ax,ss
+asm mov ds,ax
+
+}
+
+
+/*
+======================
+=
+= RLEBcompress
+=
+======================
+*/
+
+long RLEBCompress (unsigned char huge *source, long length,
+ unsigned char huge *dest, unsigned char rlebtag)
+{
+ long complength;
+ unsigned char value,count;
+ unsigned i;
+ unsigned char huge *start,huge *end;
+
+ start = dest;
+
+ end = source+length;
+
+//
+// compress it
+//
+ do
+ {
+ count = 1;
+ value = *source++;
+ while (*source == value && source<end && count<255)
+ {
+ count++;
+ source++;
+ }
+ if (count>3 || value == rlebtag)
+ {
+ //
+ // send a tag / count / value string
+ //
+ *dest++ = rlebtag;
+ *dest++ = count;
+ *dest++ = value;
+ }
+ else
+ {
+ //
+ // send byte without compressing
+ //
+ for (i=1;i<=count;i++)
+ *dest++ = value;
+ }
+
+ } while (source<end);
+
+ complength = dest-start;
+ return complength;
+}
+
+
+
+/*
+======================
+=
+= RLEBExpand
+=
+======================
+*/
+
+void RLEBExpand (unsigned char huge *source, unsigned char huge *dest,
+ long length, unsigned char rlebtag)
+{
+ unsigned char value,count;
+ unsigned i;
+ unsigned sourceseg,sourceoff,destseg,destoff,endseg,endoff;
+ unsigned char huge *end;
+
+
+//
+// expand it
+//
+#if 0
+ do
+ {
+ value = *source++;
+ if (value != rlebtag)
+ //
+ // uncompressed
+ //
+ *dest++=value;
+ else
+ {
+ //
+ // compressed string
+ //
+ count = *source++;
+ value = *source++;
+ for (i=1;i<=count;i++)
+ *dest++ = value;
+ }
+ } while (dest<end);
+#endif
+
+
+ end = dest + (length);
+ sourceseg = FP_SEG(source);
+ sourceoff = FP_OFF(source);
+ destseg = FP_SEG(dest);
+ destoff = FP_OFF(dest);
+ endseg = FP_SEG(end);
+ endoff = FP_OFF(end);
+
+
+//
+// al = source value
+// bl = tag value
+// cl = repeat counts
+// dx = scratch
+//
+// NOTE: A repeat count that produces 0xfff0 bytes can blow this!
+//
+
+asm mov bx,WORD PTR rlebtag
+asm mov si,sourceoff
+asm mov di,destoff
+asm mov es,destseg
+asm mov ds,sourceseg
+asm xor ch,ch
+
+expand:
+asm lodsb
+asm cmp al,bl
+asm je repeat
+asm stosb
+asm jmp next
+
+repeat:
+asm lodsb
+asm mov cl,al // repeat count
+asm lodsb // repeat value
+asm rep stosb
+
+next:
+
+asm cmp si,0x10 // normalize ds:si
+asm jb sinorm
+asm mov ax,si
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm mov dx,ds
+asm add dx,ax
+asm mov ds,dx
+asm and si,0xf
+sinorm:
+asm cmp di,0x10 // normalize es:di
+asm jb dinorm
+asm mov ax,di
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm shr ax,1
+asm mov dx,es
+asm add dx,ax
+asm mov es,dx
+asm and di,0xf
+dinorm:
+
+asm cmp di,ss:endoff
+asm jne expand
+asm mov ax,es
+asm cmp ax,ss:endseg
+asm jb expand
+
+asm mov ax,ss
+asm mov ds,ax
+
+
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////
+
+
+#if 1
+/*
+==================
+=
+= CarmackCompress
+=
+= Compress a string of words
+=
+==================
+*/
+
+#define NEARTAG 0xa7
+#define FARTAG 0xa8
+
+long CarmackCompress (unsigned far *source,long length,
+ unsigned far *dest)
+{
+ unsigned ch,chhigh;
+ unsigned far *instart, far *inptr, far *inscan,
+ far *stopscan, far *outptr;
+ unsigned far *bestscan, beststring;
+ unsigned dist,maxstring,string,outlength;
+ unsigned nearrepeats,farrepeats;
+ unsigned dups,count;
+ unsigned newwords;
+
+//
+// this compression method produces a stream of words
+// If the words high byte is NEARTAG or FARTAG, the low byte is a word
+// copy count from the a position specified by either the next byte
+// or the next word, respectively. A copy count of 0 means to insert the
+// next byte as the low byte of the tag into the output
+//
+
+
+//
+// set up
+//
+ instart = inptr = source;
+ outptr = dest;
+
+ outlength = 0;
+ length = (length+1)/2;
+
+ nearrepeats = farrepeats = dups = 0;
+ count = 10;
+ newwords = 0;
+//
+// compress
+//
+ do
+ {
+ ch = *inptr;
+
+//
+// scan from start for patterns that match current data
+//
+ beststring = 0;
+ for (inscan = instart; inscan<inptr; inscan++)
+ {
+ if (*inscan != ch)
+ continue;
+
+ maxstring = inptr-inscan;
+ if (maxstring > length)
+ maxstring = length;
+ if (maxstring > 255)
+ maxstring = 255;
+
+ string = 1;
+ while (*(inscan+string) == *(inptr+string) && string<maxstring)
+ string++;
+
+ if (string >= beststring)
+ {
+ beststring = string;
+ bestscan = inscan;
+ }
+ }
+
+ if (beststring > 1 && inptr-bestscan <= 255)
+ {
+ // near string
+ *outptr++ = beststring + (NEARTAG*256);
+ *((unsigned char far *)outptr)++ = inptr-bestscan;
+ outlength += 3;
+ nearrepeats++;
+ inptr += beststring;
+ length -= beststring;
+ }
+ else if (beststring > 2)
+ {
+ // far string
+ *outptr++ = beststring + (FARTAG*256);
+ *outptr++ = bestscan-instart;
+ outlength += 4;
+ farrepeats++;
+ inptr += beststring;
+ length -= beststring;
+ }
+ else // no compression
+ {
+ chhigh = ch>>8;
+ if (chhigh == NEARTAG || chhigh == FARTAG)
+ {
+ // special case of encountering a
+ // tag word in the data stream
+ // send a length of 0, and follow it with the real low byte
+ *outptr++ = ch & 0xff00;
+ *((unsigned char far *)outptr)++ = ch&0xff;
+ outlength += 3;
+ dups++;
+ }
+ else
+ {
+ *outptr++ = ch;
+ outlength += 2;
+ }
+ inptr++;
+ length--;
+ newwords++;
+ }
+
+ if (!--count)
+ {
+ static char cc[2]="-";
+ cc[0]^='+'^'-';
+ print(cc);
+ sx--;
+
+ count = 10;
+
+ if (keydown[1])
+ {
+ while(keydown[1]);
+ return 0;
+ }
+ }
+ if (length<0)
+ Quit ("Length < 0!");
+ } while (length);
+ #if 0
+ printf ("%u near patterns\n",nearrepeats);
+ printf ("%u far patterns\n",farrepeats);
+ printf ("%u new words\n",newwords);
+ printf ("%u dups\n\n",dups);
+ #endif
+ return outlength;
+}
+#else
+
+
+
+/*
+==================
+=
+= CarmackCompress
+=
+= Compress a string of words
+=
+==================
+*/
+
+#define NEARTAG 0xa7
+#define FARTAG 0xa8
+
+long CarmackCompress (unsigned far *source,long length,
+ unsigned far *dest)
+{
+ unsigned wch,chhigh;
+ unsigned inptrx;
+ unsigned far *instart, far *inptr, far *inscan,
+ far *stopscan, far *outptr;
+ unsigned far *bestscan, beststring;
+ unsigned dist,maxstring,string,outlength;
+ unsigned nearrepeats,farrepeats;
+ unsigned dups,count;
+ unsigned newwords;
+
+//
+// this compression method produces a stream of words
+// If the words high byte is NEARTAG or FARTAG, the low byte is a word
+// copy count from the a position specified by either the next byte
+// or the next word, respectively. A copy count of 0 means to insert the
+// next byte as the low byte of the tag into the output
+//
+
+
+//
+// set up
+//
+ instart = inptr = bestscan = source;
+ outptr = dest;
+
+ outlength = 0;
+ length = (length+1)/2;
+
+ nearrepeats = farrepeats = dups = 0;
+ count = 10;
+ newwords = 0;
+//
+// compress
+//
+ do
+ {
+ wch = *inptr;
+ inptrx = FP_OFF(inptr)+2; // convienient for cmpsw
+
+//
+// scan from start for patterns that match current data
+//
+//================
+
+//
+// ax:
+// bx: beststring
+// cx: repeat counts
+// dx: holding spot for inscan repeat count
+// si: inptr
+// di: inscan
+//
+asm xor bx,bx // beststring = 0
+
+asm les di,[instart] // start looking for an identical string
+ // at the start of uncompressed text
+asm mov ax,es
+asm mov ds,ax // both DS and ES point to uncompressed data
+
+asm mov cx,WORD PTR [inptr]
+asm sub cx,di
+asm shr cx,1 // cx = words between inscan and inptr
+
+search:
+asm mov ax,[wch] // current uncompressed word
+asm repne scasw // search from DI for up to CX words for a
+ // first char match
+asm jcxz done // no more to search
+
+asm mov dx,cx // save off remaining repeat count
+ // the number in CX is the remaining words
+ // to search for a long pattern
+asm mov si,[inptrx] // SI is the current source data
+ // DI is the match in previously compressed
+ // data
+asm mov ax,di // save off DI so we can back up after scan
+asm repe cmpsw // decrement CX for each additional match
+asm jne ended
+asm dec cx // the search ended because of CX, not bad match
+ended:
+asm mov di,ax // back to original spot
+asm mov ax,dx
+asm sub ax,cx // AX is the total number of matching words
+asm cmp ax,bx // more chars than beststring?
+asm jb next
+asm mov bx,ax
+asm mov WORD PTR [bestscan],di // bestscan is start of the best match+2
+
+next:
+asm mov cx,dx // restore the remaining count
+asm jmp search
+
+done:
+asm mov ax,ss
+asm mov ds,ax
+asm mov [beststring],bx // save out the register variable
+asm dec bx
+asm sub WORD PTR [bestscan],2 // scasw incremented past start
+//================
+
+ if (beststring>length)
+ beststring = length;
+
+ if (beststring > 1 && inptr-bestscan <= 255)
+ {
+ // near string
+ *outptr++ = beststring + (NEARTAG*256);
+ *((unsigned char far *)outptr)++ = inptr-bestscan;
+ outlength += 3;
+ nearrepeats++;
+ inptr += beststring;
+ length -= beststring;
+ }
+ else if (beststring > 2)
+ {
+ // far string
+ *outptr++ = beststring + (FARTAG*256);
+ *outptr++ = bestscan-instart;
+ outlength += 4;
+ farrepeats++;
+ inptr += beststring;
+ length -= beststring;
+ }
+ else // no compression
+ {
+ chhigh = wch>>8;
+ if (chhigh == NEARTAG || chhigh == FARTAG)
+ {
+ // special case of encountering a
+ // tag word in the data stream
+ // send a length of 0, and follow it with the real low byte
+ *outptr++ = wch & 0xff00;
+ *((unsigned char far *)outptr)++ = wch&0xff;
+ outlength += 3;
+ dups++;
+ }
+ else
+ {
+ *outptr++ = wch;
+ outlength += 2;
+ }
+ inptr++;
+ length--;
+ newwords++;
+ }
+
+ if (!--count)
+ {
+ static char cc[2]="-";
+ cc[0]^='+'^'-';
+ print(cc);
+ sx--;
+
+ count = 10;
+
+ if (keydown[1])
+ {
+ while(keydown[1]);
+ return 0;
+ }
+ }
+ } while (length);
+#if 0
+ printf ("\r%u near patterns\n",nearrepeats);
+ printf ("%u far patterns\n",farrepeats);
+ printf ("%u new words\n",newwords);
+ printf ("%u dups\n\n",dups);
+#endif
+ return outlength;
+}
+#endif
+
+
projects / 16.git / blobdiff