home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / SBWBS.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  14KB  |  513 lines
  1. /* Copyright (C) 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* sbwbs.c */
  20. /* Burrows/Wheeler block sorting compression filters */
  21. #include "stdio_.h"
  22. #include "memory_.h"
  23. #include <stdlib.h>        /* for qsort */
  24. #include "gdebug.h"
  25. #include "strimpl.h"
  26. #include "sfilter.h"
  27. #include "sbwbs.h"
  28.  
  29. /* ------ Move-to-front (MTF) encode and decode ------ */
  30.  
  31. private_st_MTF_state();
  32.  
  33. #define ss ((stream_MTF_state *)st)
  34.  
  35. /* Initialize */
  36. private int
  37. s_MTF_init(stream_state *st)
  38. {    int i;
  39.     for ( i = 0; i < 256; i++ )
  40.         ss->prev[i] = (byte)i;
  41.     return 0;
  42. }
  43.  
  44. /* Encode a buffer */
  45. private int
  46. s_MTFE_process(stream_state *st, stream_cursor_read *pr,
  47.   stream_cursor_write *pw, bool last)
  48. {    register const byte *p = pr->ptr;
  49.     register byte *q = pw->ptr;
  50.     const byte *rlimit = pr->limit;
  51.     uint count = rlimit - p;
  52.     uint wcount = pw->limit - q;
  53.     int status =
  54.         (count < wcount ? 0 :
  55.          (rlimit = p + wcount, 1));
  56.     while ( p < rlimit )
  57.     {    byte b = *++p;
  58.         byte prev = b, repl;
  59.         int i;
  60.         for ( i = 0; (repl = ss->prev[i]) != b; i++ )
  61.             ss->prev[i] = prev, prev = repl;
  62.         ss->prev[i] = prev;
  63.         *++q = (byte)i;
  64.     }
  65.     pr->ptr = p;
  66.     pw->ptr = q;
  67.     return status;
  68. }
  69.  
  70. /* Stream template */
  71. const stream_template s_MTFE_template =
  72. {    &st_MTF_state, s_MTF_init, s_MTFE_process, 1, 1
  73. };
  74.  
  75. /* Decode a buffer */
  76. private int
  77. s_MTFD_process(stream_state *st, stream_cursor_read *pr,
  78.   stream_cursor_write *pw, bool last)
  79. {    register const byte *p = pr->ptr;
  80.     register byte *q = pw->ptr;
  81.     const byte *rlimit = pr->limit;
  82.     uint count = rlimit - p;
  83.     uint wcount = pw->limit - q;
  84.     int status =
  85.         (count < wcount ? 0 :
  86.          (rlimit = p + wcount, 1));
  87.     while ( p < rlimit )
  88.     {    byte b = *++p;
  89.         byte first;
  90.         *++q = first = ss->prev[b];
  91. sw:        switch ( b )
  92.         {
  93.         default:
  94.             ss->prev[b] = ss->prev[b - 1];
  95.             ss->prev[b - 1] = ss->prev[b - 2];
  96.             ss->prev[b - 2] = ss->prev[b - 3];
  97.             ss->prev[b - 3] = ss->prev[b - 4];
  98.             if ( (b -= 4) != 0 )
  99.                 goto sw;
  100.             ss->prev[0] = first;
  101.             break;
  102.         case 3:
  103.             ss->prev[3] = ss->prev[2];
  104.         case 2:
  105.             ss->prev[2] = ss->prev[1];
  106.         case 1:
  107.             ss->prev[1] = ss->prev[0];
  108.             ss->prev[0] = first;
  109.         case 0:
  110.             ;
  111.         }
  112.     }
  113.     pr->ptr = p;
  114.     pw->ptr = q;
  115.     return status;
  116. }
  117.  
  118. /* Stream template */
  119. const stream_template s_MTFD_template =
  120. {    &st_MTF_state, s_MTF_init, s_MTFD_process, 1, 1
  121. };
  122.  
  123. #undef ss
  124.  
  125. /* ------ Common code for streams that buffer a block ------ */
  126.  
  127. private_st_buffered_state();
  128.  
  129. #define ss ((stream_buffered_state *)st)
  130.  
  131. /* Initialize */
  132. private int
  133. s_buffered_no_block_init(stream_state *st)
  134. {    ss->buffer = 0;
  135.     ss->filling = true;
  136.     ss->bpos = 0;
  137.     return 0;
  138. }
  139. private int
  140. s_buffered_block_init(stream_state *st)
  141. {    s_buffered_no_block_init(st);
  142.     ss->buffer = gs_alloc_bytes(st->memory, ss->BlockSize, "buffer");
  143.     if ( ss->buffer == 0 )
  144.         return ERRC;        /****** WRONG ******/
  145.     return 0;
  146. }
  147.  
  148. /* Continue filling the buffer if needed. */
  149. /* Return 0 if the buffer isn't full yet, 1 if it is full or if */
  150. /* we reached the end of input data. */
  151. /* In the latter case, also set filling = false. */
  152. /* Note that this procedure doesn't take pw as an argument. */
  153. private int
  154. s_buffered_process(stream_state *st, stream_cursor_read *pr, bool last)
  155. {    register const byte *p = pr->ptr;
  156.     const byte *rlimit = pr->limit;
  157.     uint count = rlimit - p;
  158.     uint left = ss->bsize - ss->bpos;
  159.     if ( !ss->filling )
  160.         return 1;
  161.     if ( left < count )
  162.         count = left;
  163.     if_debug3('w', "[w]buffering %d bytes to position %d, last = %s\n",
  164.           count, ss->bpos, (last ? "true" : "false"));
  165.     memcpy(ss->buffer + ss->bpos, p + 1, count);
  166.     pr->ptr = p += count;
  167.     ss->bpos += count;
  168.     if ( ss->bpos == ss->bsize || (p == rlimit && last) )
  169.     {    ss->filling = false;
  170.         return 1;
  171.     }
  172.     return 0;
  173. }
  174.  
  175. /* Release */
  176. private void
  177. s_buffered_release(stream_state *st)
  178. {    gs_free_object(st->memory, ss->buffer, "buffer");
  179. }
  180.  
  181. #undef ss
  182.  
  183. /* ------ Common code for Burrows/Wheeler block sorting filters ------ */
  184.  
  185. private_st_BWBS_state();
  186. private void s_BWBS_release(P1(stream_state *));
  187.  
  188. #define ss ((stream_BWBS_state *)st)
  189.  
  190. /* Initialize */
  191. private int
  192. bwbs_init(stream_state *st, uint osize)
  193. {    int code;
  194.     ss->bsize = ss->BlockSize;
  195.     code = s_buffered_block_init(st);
  196.     if ( code != 0 )
  197.         return code;
  198.     ss->offsets = (void *)gs_alloc_bytes(st->memory, osize,
  199.                          "BWBlockSort offsets");
  200.     if ( ss->offsets == 0 )
  201.     {    s_BWBS_release(st);
  202.         return ERRC;        /****** WRONG ******/
  203.     }
  204.     ss->I = -1;        /* haven't read I yet */
  205.     return 0;
  206. }
  207.  
  208. /* Release the filter. */
  209. private void
  210. s_BWBS_release(stream_state *st)
  211. {    gs_free_object(st->memory, ss->offsets, "BWBlockSort offsets");
  212.     s_buffered_release(st);
  213. }
  214.  
  215. /* ------ BWBlockSortEncode filter ------ */
  216.  
  217. /* Initialize */
  218. private int
  219. s_BWBSE_init(stream_state *st)
  220. {    return bwbs_init(st, ss->BlockSize * sizeof(int));
  221. }
  222.  
  223. /* Compare two rotated strings for sorting. */
  224. private stream_BWBS_state *bwbs_compare_ss;
  225. private int
  226. bwbs_compare_rotations(const void *p1, const void *p2)
  227. {    const byte *buffer = bwbs_compare_ss->buffer;
  228.     const byte *s1 = buffer + *(const int *)p1;
  229.     const byte *s2 = buffer + *(const int *)p2;
  230.     const byte *start1;
  231.     const byte *end;
  232.     int swap;
  233.     if ( *s1 != *s2 )
  234.         return (*s1 < *s2 ? -1 : 1);
  235.     if ( s1 < s2 )
  236.         swap = 1;
  237.     else
  238.     {    const byte *t = s1; s1 = s2; s2 = t;
  239.         swap = -1;
  240.     }
  241.     start1 = s1;
  242.     end = buffer + bwbs_compare_ss->N;
  243.     for ( s1++, s2++; s2 < end; s1++, s2++ )
  244.       if ( *s1 != *s2 )
  245.         return (*s1 < *s2 ? -swap : swap);
  246.     s2 = buffer;
  247.     for ( ; s1 < end; s1++, s2++ )
  248.       if ( *s1 != *s2 )
  249.         return (*s1 < *s2 ? -swap : swap);
  250.     s1 = buffer;
  251.     for ( ; s1 < start1; s1++, s2++ )
  252.       if ( *s1 != *s2 )
  253.         return (*s1 < *s2 ? -swap : swap);
  254.     return 0;
  255. }
  256. /* Sort the strings. */
  257. private void
  258. bwbse_sort(const byte *buffer, uint *indices, int N)
  259. {    offsets_full Cs;
  260. #define C Cs.v
  261.     /* Sort the strings.  We start with a radix sort. */
  262.     uint sum = 0, j, ch;
  263.     memset(C, 0, sizeof(Cs));
  264.     for ( j = 0; j < N; j++ )
  265.         C[buffer[j]]++;
  266.     for ( ch = 0; ch <= 255; ch++ )
  267.     {    sum += C[ch];
  268.         C[ch] = sum - C[ch];
  269.     }
  270.     for ( j = 0; j < N; j++ )
  271.         indices[C[buffer[j]]++] = j;
  272.     /* Now C[ch] = the number of strings that start */
  273.     /* with a character less than or equal to ch. */
  274.     sum = 0;
  275.     /* qsort each bucket produced by the radix sort. */
  276.     for ( ch = 0; ch <= 255; sum = C[ch], ch++ )
  277.         qsort(indices + sum, C[ch] - sum,
  278.               sizeof(*indices),
  279.               bwbs_compare_rotations);
  280. #undef C
  281. }
  282.  
  283. /* Encode a buffer */
  284. private int
  285. s_BWBSE_process(stream_state *st, stream_cursor_read *pr,
  286.   stream_cursor_write *pw, bool last)
  287. {    register byte *q = pw->ptr;
  288.     byte *wlimit = pw->limit;
  289.     uint wcount = wlimit - q;
  290.     uint *indices = ss->offsets;
  291.     if ( ss->filling )
  292.     {    int status, j, N;
  293.         byte *buffer = ss->buffer;
  294.         if ( wcount < sizeof(int) * 2 )
  295.             return 1;
  296.         /* Continue filling the buffer. */
  297.         status = s_buffered_process(st, pr, last);
  298.         if ( !status )
  299.             return 0;
  300.         ss->N = N = ss->bpos;
  301.         /* We reverse the string before encoding it, */
  302.         /* so it will come out of the decoder correctly. */
  303.         for ( j = N / 2 - 1; j >= 0; j-- )
  304.         {    byte *p0 = &buffer[j];
  305.             byte *p1 = &buffer[N - 1 - j];
  306.             byte b = *p0;
  307.             *p0 = *p1;
  308.             *p1 = b;
  309.         }
  310.         /* Save st in a static, because that's the only way */
  311.         /* we can pass it to the comparison procedure (ugh). */
  312.         bwbs_compare_ss = ss;
  313.         /* Sort the strings. */
  314.         bwbse_sort(buffer, indices, N);
  315.         /* Find the unrotated string. */
  316.         for ( j = 0; j < N; j++ )
  317.           if ( indices[j] == 0 )
  318.         {    ss->I = j;
  319.             break;
  320.         }
  321.         for ( j = sizeof(int); --j >= 0; )
  322.             *++q = (byte)(N >> (j * 8));
  323.         for ( j = sizeof(int); --j >= 0; )
  324.             *++q = (byte)(ss->I >> (j * 8));
  325.         ss->bpos = 0;
  326.     }
  327.     /* We're reading out of the buffer, writing the permuted string. */
  328.     while ( q < wlimit && ss->bpos < ss->N )
  329.     {    int i = indices[ss->bpos++];
  330.         *++q = ss->buffer[(i == 0 ? ss->N - 1 : i - 1)];
  331.     }
  332.     if ( ss->bpos == ss->N )
  333.     {    ss->filling = true;
  334.         ss->bpos = 0;
  335.     }
  336.     pw->ptr = q;
  337.     if ( q == wlimit )
  338.         return 1;
  339.     return 0;
  340. }
  341.  
  342. /* Stream template */
  343. const stream_template s_BWBSE_template =
  344. {    &st_BWBS_state, s_BWBSE_init, s_BWBSE_process, sizeof(int) * 2, 1, s_BWBS_release
  345. };
  346.  
  347. /* ------ BWBlockSortDecode filter ------ */
  348.  
  349. /*
  350.  * Letting S[0..N-1] be the data block before depermutation, we need
  351.  * a table P[0..N-1] that maps the index i to O(S[i],i), where O(c,i) is
  352.  * the number of occurrences of S[i] in S before position i.
  353.  * We observe that for a fixed c, O(c,i) is monotonic with i,
  354.  * and falls in the range 0 .. i-1; consequently, if 0 <= i <= j,
  355.  * 0 <= O(c,j) - O(c,i) <= j - i.  Proceeding from this observation,
  356.  * rather than allocate an entire int to each entry of P,
  357.  * we construct three tables as follows:
  358.  *    P2[k,c] = O(c,k*65536) for k = 0 .. N/65536;
  359.  *        each entry requires an int.
  360.  *    P1[k,c] = O(c,k*4096) - P2[k/16,c] for k = 0 .. N/4096;
  361.  *        each entry requires 16 bits.
  362.  *    P[i] = O(S[i],i) - P1[i/4096,S[i]] for i = 0 .. N-1;
  363.  *        each entry requires 12 bits.
  364.  */
  365. /*typedef struct { uint v[256]; } offsets_full;*/    /* in sbwbs.h */
  366. typedef struct { bits16 v[256]; } offsets_4k;
  367. #if arch_sizeof_int > 2
  368. #  define ceil_64k(n) (((n) + 0xffff) >> 16)
  369. #else
  370. #  define ceil_64k(n) 1
  371. #endif
  372. #define ceil_4k(n) (((n) + 0xfff) >> 12)
  373.  
  374. /* Initialize */
  375. private int
  376. s_BWBSD_init(stream_state *st)
  377. {    uint bsize = ss->BlockSize;
  378.     return bwbs_init(st,
  379.              ceil_64k(bsize) * sizeof(offsets_full) +
  380.              ceil_4k(bsize) * sizeof(offsets_4k) +
  381.              ((bsize + 1) >> 1) * 3);
  382. }
  383.  
  384. /* Decode a buffer */
  385. private void
  386. bwbsd_construct_offsets(P5(stream_BWBS_state *, offsets_full *, offsets_4k *,
  387.   byte *, int));
  388. private int
  389. s_BWBSD_process(stream_state *st, stream_cursor_read *pr,
  390.   stream_cursor_write *pw, bool last)
  391. {    register const byte *p = pr->ptr;
  392.     const byte *rlimit = pr->limit;
  393.     uint count = rlimit - p;
  394.     register byte *q = pw->ptr;
  395.     byte *wlimit = pw->limit;
  396.     uint BlockSize = ss->BlockSize;
  397.     offsets_full *po64k = ss->offsets;
  398.     offsets_4k *po4k = (offsets_4k *)(po64k + ceil_64k(BlockSize));
  399.     byte *po1 = (byte *)(po4k + ceil_4k(BlockSize));
  400.     if ( ss->I < 0 )
  401.     {    /* Read block parameters */
  402.         int I, N, j;
  403.         if ( count < sizeof(int) * 2 )
  404.             return 0;
  405.         for ( N = 0, j = 0; j < sizeof(int); j++ )
  406.             N = (N << 8) + *++p;
  407.         for ( I = 0, j = 0; j < sizeof(int); j++ )
  408.             I = (I << 8) + *++p;
  409.         ss->N = N;
  410.         ss->I = I;
  411.         if_debug2('w', "[w]N=%d I=%d\n", N, I);
  412.         pr->ptr = p;
  413.         if ( N < 0 || N > ss->BlockSize || I < 0 || I >= N )
  414.             return ERRC;
  415.         if ( N == 0 )
  416.             return EOFC;
  417.         count -= sizeof(int) * 2;
  418.         ss->bpos = 0;
  419.         ss->bsize = N;
  420.     }
  421.     if ( ss->filling )
  422.     {    /* Continue filling the buffer. */
  423.         if ( !s_buffered_process(st, pr, last) )
  424.             return 0;
  425.         /* Construct the inverse sort order. */
  426.         bwbsd_construct_offsets(ss, po64k, po4k, po1, ss->bsize);
  427.         ss->bpos = 0;
  428.         ss->i = ss->I;
  429.     }
  430.     /* We're reading out of the buffer. */
  431.     while ( q < wlimit && ss->bpos < ss->bsize )
  432.     {    int i = ss->i;
  433.         byte b = ss->buffer[i];
  434.         uint d;
  435.         const byte *pd = &po1[(i >> 1) + i];
  436.         *++q = b;
  437.         if ( !(i & 1) )
  438.             d = ((uint)pd[0] << 4) + (pd[1] >> 4);
  439.         else
  440.             d = ((pd[0] & 0xf) << 8) + pd[1];
  441.         ss->i = po64k[i >> 16].v[b] + po4k[i >> 12].v[b] + d;
  442.         ss->bpos++;
  443.     }
  444.     if ( ss->bpos == ss->bsize )
  445.     {    ss->I = -1;
  446.         ss->filling = true;
  447.     }
  448.     pw->ptr = q;
  449.     if ( q == wlimit )
  450.         return 1;
  451.     return 0;
  452. }
  453.  
  454. #undef ss
  455.  
  456. /* Stream template */
  457. const stream_template s_BWBSD_template =
  458. {    &st_BWBS_state, s_BWBSD_init, s_BWBSD_process, 1, sizeof(int) * 2, s_BWBS_release
  459. };
  460.  
  461. /* Construct the decoding tables. */
  462. private void
  463. bwbsd_construct_offsets(stream_BWBS_state *ss, offsets_full *po64k,
  464.   offsets_4k *po4k, byte *po1, int N)
  465. {    offsets_full Cs;
  466. #define C Cs.v
  467.     uint i1;
  468.     byte *b = ss->buffer;
  469.     offsets_full *p2 = po64k - 1;
  470.     offsets_4k *p1 = po4k;
  471.     byte *p = po1;
  472.     memset(C, 0, sizeof(Cs));
  473.     /* If the block length is odd, store a 0 at the end. */
  474.     if ( N & 1 )
  475.       b[N - 1] = 0;
  476.     for ( i1 = 0; i1 < ceil_4k(N); i1++, p1++ )
  477.       {    int j;
  478.         if ( !(i1 & 15) )
  479.           *++p2 = Cs;
  480.         for ( j = 0; j < 256; j++ )
  481.           p1->v[j] = C[j] - p2->v[j];
  482.         j = (N + 1 - (i1 << 12)) >> 1;
  483.         if ( j > 4096/2 )
  484.           j = 4096/2;
  485.         for ( ; j > 0; j--, b += 2, p += 3 )
  486.            {    byte b0 = b[0];
  487.             uint d0 = C[b0]++ - (p1->v[b0] + p2->v[b0]);
  488.             byte b1 = b[1];
  489.             uint d1 = C[b1]++ - (p1->v[b1] + p2->v[b1]);
  490.             p[0] = d0 >> 4;
  491.             p[1] = (byte)((d0 << 4) + (d1 >> 8));
  492.             p[2] = (byte)d1;
  493.            }
  494.        }
  495.     if ( N & 1 )
  496.       C[0]--;
  497.     /* Compute the cumulative totals in C. */
  498.     {    int sum = 0, ch;
  499.         for ( ch = 0; ch <= 255; ch++ )
  500.         {    sum += C[ch];
  501.             C[ch] = sum - C[ch];
  502.         }
  503.     }
  504.     /* Add the C values back into the 64K table, */
  505.     /* which saves an addition of C[b] in the decoding loop. */
  506.     {    int i2, ch;
  507.         for ( p2 = po64k, i2 = ceil_64k(N); i2 > 0; p2++, i2-- )
  508.           for ( ch = 0; ch < 256; ch++ )
  509.             p2->v[ch] += C[ch];
  510.     }
  511. #undef C
  512. }
  513.