home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 1 / ARM_CLUB_CD.iso / contents / apps / archive / progs / squish / Misc / MCfns
Encoding:
Text File  |  1994-08-03  |  6.7 KB  |  219 lines
  1. /*
  2.    The following are a couple of 'pseudo-assembler' functions written during development of the assembler
  3.    mcomp & mdeco LZW compression functions, whose code can be found in !Squish.s.Core.
  4.    For testing or further development, mccomp & mcdeco, below, may be used in place of mcomp & mdeco.
  5.    Pseudo-assembler means that they have been written in C with a mind to being easy to translate directly
  6.    into assembler, thus each line will typically mimic one or two ARM instructions, or simple code
  7.    fragments (eg a loop used to zero a region of memory).
  8.    This makes development including experimentation & debugging of the algorithm itself much simpler.
  9.    The C compiler being efficient, this code is also reasonably fast - usually running at between 50% &
  10.    75% of the optimised assembler equivalent.
  11.    When using such a technique, there are a few points to bear in mind:
  12.    Variables mimicing registers should be unsigned int's;
  13.    When copying an assembler comparison, be careful about the sign - eg GT being signed requires that the
  14.    C analogue first has its arguments cast to signed int;
  15.    Similarly be careful about sign in relation to shifts - ASL, ASR require a cast of C argument to signed
  16.    int; LSR, LSL don't;
  17.    Same applies to divisions by powers of 2 in C.
  18.    On an assembler data store or load, if using LDM or STM be very careful about word alignment - if
  19.    pointer not necessarily word aligned, ARM will round it down; in C analogue, ensure you explicitly
  20.    round the argument down (eg use (pointer & ~3) instead of just pointer).
  21.  */
  22.  
  23. static char m[] = {0x00, 0x3c, 0x18, 0x54, 0x30, 0x0c, 0x48, 0x24};
  24.  
  25. /*
  26.    args: input, input size, output, workspace
  27.    returns: number of output bytes written
  28.  */
  29. int mccomp(char *in, int insz, char *out, char *ws)
  30. {
  31. /*
  32.   vbles:  bit index, chunk size, tag, tag upper bound (exclusive), output address (=out+bin/8, not
  33.       necessarily word aligned in value, but assumes will be rounded down when accessed by a ldm/stm
  34.       instruction in assembler code, or manually, in pseudo assembler {ie C below}), index into
  35.       workspace, triplet, scratch 1, scratch 2, last chunk (may be byte or tag), workspace prime table
  36.           length constant (nb can't alter this unless also alter workspace size used by clients)
  37.  */
  38.   unsigned int bin, chsz, tag, tagbd, oa, i, tri, t1, t2, lc, wspc;
  39.   unsigned int oldout; /*Initial out, only needed once upon fn return, so in assembler, store in memory.*/
  40.   unsigned int oldbin; /*old bit index, only needed on a tag reset, so in assembler, store in memory.*/
  41.  
  42.   oldout = (int)out;
  43.   wspc = 5119;
  44.  
  45.   *out++ = 0x1f;    /*Write 24-bit flag.*/
  46.   *out++ = 0x9d;
  47.   *out++ = 0x8c;
  48.  
  49.   lc = *in++;        /*Get first byte of input,*/
  50.   insz--;               /*so one less byte to go.*/
  51.   bin = ((int)out&3)*8; /*Initialise bin, from out ptr above 24-bit flag, rounded down to word boundary.*/
  52.   oldbin = bin;
  53.   while ((int)out&3) *out++ = 0;
  54.   if (bin) out-=4;    /*Reset out to point to address above 24-bit flag, then rounded down to
  55.               word alignment, so that out+bin/8 points to first bit above 24-bit flag.*/
  56.   mccomp_resettags:
  57.  
  58.   tag = 257;
  59.   tagbd = 512;
  60.   chsz = 9;
  61.   t1 = (int)(ws+wspc*4-4);
  62.   for (; t1>=(int)ws; t1-=4) *(int *)t1 = 0;    /*Fill workspace with 0's, to reset all tags.*/
  63.  
  64.   mccomp_loop:
  65.  
  66.   insz--;
  67.   if ((signed int)insz<0) {
  68.     oa = (int)out + bin/8;
  69.     t1 = *(int *)(oa&~3);
  70.     t2 = bin&31;
  71.     if (t2==0) t1 = lc;
  72.     else {
  73.       t1 = t1 | (lc<<t2);
  74.       lc = lc >> (32-t2);
  75.     }
  76.     *(int *)((oa&~3)+0) = t1;
  77.     *(int *)((oa&~3)+4) = lc;
  78.     bin += chsz;
  79.     out += (bin+7)/8;
  80.     return (int)out - oldout;
  81.   }
  82.  
  83.   tri = *in++;
  84.   i = lc ^ 16*tri;
  85.   tri = tri | 256*lc;
  86.   t1 = *(int *)(ws + 4*i);
  87.   if (t1 == 0) goto mccomp_unknownseq;
  88.   if (tri == t1/4096) {
  89.     lc = t1 & 0xfff;
  90.     goto mccomp_loop;
  91.   }
  92.   if (i == 0) t1 = 1;
  93.   else t1 = wspc-i;
  94.   mccomp_scanws:
  95.   i -= t1;
  96.   if ((signed int)i < 0) i+=wspc;
  97.   t2 = *(int *)(ws + 4*i);
  98.   if (t2 == 0) goto mccomp_unknownseq;
  99.   if (tri == t2/4096) {
  100.     lc = t2 & 0xfff;
  101.     goto mccomp_loop;
  102.   }
  103.   goto mccomp_scanws;
  104.  
  105.   mccomp_unknownseq:
  106.   oa = (int)out + bin/8;
  107.   t1 = *(int *)(oa&~3);
  108.   t2 = bin&31;
  109.   if (t2==0) t1 = lc;
  110.   else {
  111.     t1 = t1 | (lc<<t2);
  112.     lc = lc >> (32-t2);
  113.   }
  114.   *(int *)((oa&~3)+0) = t1;
  115.   *(int *)((oa&~3)+4) = lc;
  116.   bin += chsz;
  117.   lc = tri & 255;
  118.   if (tag >= 4096) {
  119.     oa = (int)out + bin/8;
  120.     t1 = *(int *)(oa&~3);
  121.     t2 = bin&31;
  122.     if (t2==0) t1 = 256;
  123.     else {
  124.       tag = 256;      /*tag no longer needed, so can temporarily use as a third scratch register.*/
  125.       t1 = t1 | (tag<<t2);
  126.       t2 = tag >> (32-t2);
  127.     }
  128.     *(int *)((oa&~3)+0) = t1;
  129.     *(int *)((oa&~3)+4) = t2;
  130.     bin += chsz;
  131.     t1 = (bin - oldbin)/4 & 7;
  132.     t1 = m[t1];
  133.     t2 = (bin+7)&~7;      /*round up to a byte - intervening bits will already be zero*/
  134.     bin += t1;
  135.     oldbin = bin;
  136.     mccomp_appendzeros:
  137.     *(out + t2/8) = 0;
  138.     t2+=8;
  139.     if (t2 < bin) goto mccomp_appendzeros;
  140.     if ((t2&24) != 0) goto mccomp_appendzeros;    /*initialise bits upto word boundary to zero,
  141.                           for subsequent writes, as at algo start*/
  142.     goto mccomp_resettags;
  143.   }
  144.  
  145.   tri = tag | 4096*tri;
  146.   *(int *)(ws + 4*i) = tri;
  147.   if (tag >= tagbd) {
  148.     chsz++;
  149.     tagbd *= 2;
  150.   }
  151.   tag++;
  152.   goto mccomp_loop;
  153. }
  154.  
  155. /*
  156.    args: input, input size, output, workspace
  157.  */
  158. BOOL mcdeco(char *in, int insz, char *out, char *ws)
  159. {
  160. /*
  161.   vbles: bit index, old bit index, chunk, chunk size, tag, maximum tag, scratch 1, scratch 2
  162.  */
  163.   unsigned int bin, oldbin, ch, chsz, tag, tagmx, t1, t2;
  164.  
  165.   if (in[0]!=0x1f || in[1]!=0x9d || in[2]!=0x8c) return FALSE;
  166.   ws = ws - 1024;       /*as lowest int index will be 256*/
  167.  
  168.   in    += 3;           /*step over 24-bit flag*/
  169.   insz  -= 3;           /*compensate insz*/
  170.   bin    = (int)in & 3;
  171.   in    -= bin;         /*round in down to word boundary*/
  172.   insz  += bin;         /*compensate insz*/
  173.   bin   *= 8;           /*bit index, bit offset to data from in*/
  174.   oldbin = bin;
  175.   insz   = insz*8 - 9;
  176.   tag    = 256;
  177.   tagmx  = 511;
  178.   chsz   = 9;
  179.  
  180.   mploop:               /*start decompression*/
  181.   if (bin>insz) return TRUE;
  182.   if (tag>tagmx) {
  183.     if (chsz<12) {
  184.       chsz++;
  185.       tagmx = 2*tagmx + 1;
  186.     }
  187.   }
  188.   if (tag<4096) *(char **)(ws + 4*tag) = out;
  189.   ch = *(int *)(in + bin/32*4);
  190.   t1 = *(int *)(in + bin/32*4 + 4);
  191.   if (bin&31) {
  192.     ch >>= (bin&31);
  193.     ch  |= t1 << (32-(bin&31));
  194.   }
  195.   ch &= tagmx;
  196.   bin += chsz;
  197.   if (ch==256) {
  198.     t1     = (bin-oldbin)/4 & 7;
  199.     bin   += m[t1];
  200.     oldbin = bin;
  201.     tag    = 256;
  202.     tagmx  = 511;
  203.     chsz   = 9;
  204.     goto mploop;
  205.   }
  206.   if (ch<256) {
  207.     *out++ = ch;
  208.     tag++;
  209.     goto mploop;
  210.   }
  211.   t1 = *(int *)(ws + 4*ch - 4);
  212.   t2 = *(int *)(ws + 4*ch);
  213.   *out++ = *(char *)t1++;
  214.   do *out++ = *(char *)t1++;
  215.   while (t1<=t2);
  216.   tag++;
  217.   goto mploop;
  218. }
  219.