1 : /******************************************************************************
2 : * $Id: rmflzw.cpp 11865 2007-08-09 11:53:57Z warmerdam $
3 : *
4 : * Project: Raster Matrix Format
5 : * Purpose: Implementation of the LZW compression algorithm as used in
6 : * GIS "Panorama"/"Integratsia" raster files. Based on implementation
7 : * of Kent Williams, but heavily modified over it. The key point
8 : * in the initial implementation is a hashing algorithm.
9 : * Author: Andrey Kiselev, dron@ak4719.spb.edu
10 : *
11 : ******************************************************************************
12 : * Copyright (c) 2007, Andrey Kiselev <dron@ak4719.spb.edu>
13 : *
14 : * Permission is hereby granted, free of charge, to any person obtaining a
15 : * copy of this software and associated documentation files (the "Software"),
16 : * to deal in the Software without restriction, including without limitation
17 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 : * and/or sell copies of the Software, and to permit persons to whom the
19 : * Software is furnished to do so, subject to the following conditions:
20 : *
21 : * The above copyright notice and this permission notice shall be included
22 : * in all copies or substantial portions of the Software.
23 : *
24 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
25 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 : * DEALINGS IN THE SOFTWARE.
31 : ******************************************************************************
32 : * COPYRIGHT NOTICE FROM THE INITIAL IMPLEMENTATION:
33 : *
34 : * The programs LZWCOM and LZWUNC, both in binary executable and source forms,
35 : * are in the public domain. No warranty is given or implied, and no
36 : * liability will be assumed by the author.
37 : *
38 : * Everyone on earth is hereby given permission to use, copy, distribute,
39 : * change, mangle, destroy or otherwise employ these programs, provided they
40 : * hurt no one but themselves in the process.
41 : *
42 : * Kent Williams
43 : * Norand Inc.
44 : * 550 2nd St S.E.
45 : * Cedar Rapids, Iowa 52401
46 : * (319) 369-3131
47 : ****************************************************************************/
48 :
49 : #include "cpl_conv.h"
50 :
51 : #include "rmfdataset.h"
52 :
53 : // Code marks that there is no predecessor in the string
54 : #define NO_PRED 0xFFFF
55 :
56 : // We are using 12-bit codes in this particular implementation
57 : #define TABSIZE 4096U
58 : #define STACKSIZE TABSIZE
59 :
60 : /************************************************************************/
61 : /* LZWStringTab */
62 : /************************************************************************/
63 :
64 : typedef struct
65 : {
66 : int bUsed;
67 : GUInt32 iNext; // hi bit is 'used' flag
68 : GUInt32 iPredecessor; // 12 bit code
69 : GByte iFollower;
70 : } LZWStringTab;
71 :
72 : /************************************************************************/
73 : /* LZWUpdateTab() */
74 : /************************************************************************/
75 :
76 0 : static void LZWUpdateTab(LZWStringTab *poCodeTab, GUInt32 iPred, char bFoll)
77 : {
78 : GUInt32 nNext;
79 :
80 : /* -------------------------------------------------------------------- */
81 : /* Hash uses the 'mid-square' algorithm. I.E. for a hash val of n bits */
82 : /* hash = middle binary digits of (key * key). Upon collision, hash */
83 : /* searches down linked list of keys that hashed to that key already. */
84 : /* It will NOT notice if the table is full. This must be handled */
85 : /* elsewhere */
86 : /* -------------------------------------------------------------------- */
87 0 : GUInt32 nLocal = (iPred + bFoll) | 0x0800;
88 0 : nLocal = (nLocal*nLocal >> 6) & 0x0FFF; // middle 12 bits of result
89 :
90 : // If string is not used
91 0 : if (poCodeTab[nLocal].bUsed == FALSE)
92 0 : nNext = nLocal;
93 : else
94 : {
95 : // If collision has occured
96 0 : while ( (nNext = poCodeTab[nLocal].iNext) != 0 )
97 0 : nLocal = nNext;
98 :
99 : // Search for free entry from nLocal + 101
100 0 : nNext = (nLocal + 101) & 0x0FFF;
101 0 : while ( poCodeTab[nNext].bUsed )
102 : {
103 0 : if ( ++nNext >= TABSIZE )
104 0 : nNext = 0;
105 : }
106 :
107 : // Put new tempnext into last element in collision list
108 0 : poCodeTab[nLocal].iNext = nNext;
109 : }
110 :
111 0 : poCodeTab[nNext].bUsed = TRUE;
112 0 : poCodeTab[nNext].iNext = 0;
113 0 : poCodeTab[nNext].iPredecessor = iPred;
114 0 : poCodeTab[nNext].iFollower = bFoll;
115 0 : }
116 :
117 : /************************************************************************/
118 : /* LZWDecompress() */
119 : /************************************************************************/
120 :
121 0 : int RMFDataset::LZWDecompress( const GByte* pabyIn, GUInt32 nSizeIn,
122 : GByte* pabyOut, GUInt32 nSizeOut )
123 : {
124 0 : GUInt32 nCount = TABSIZE - 256;
125 : GUInt32 iCode, iOldCode, iInCode;
126 0 : GByte iFinChar, bLastChar=FALSE;
127 : LZWStringTab *poCodeTab;
128 : int bBitsleft;
129 :
130 0 : if ( pabyIn == 0 ||
131 : pabyOut == 0 ||
132 : nSizeOut < nSizeIn ||
133 : nSizeIn < 2 )
134 0 : return 0;
135 :
136 : // Allocate space for the new table and pre-fill it
137 0 : poCodeTab = (LZWStringTab *)CPLMalloc( TABSIZE * sizeof(LZWStringTab) );
138 0 : if ( !poCodeTab )
139 0 : return 0;
140 0 : memset( poCodeTab, 0, TABSIZE * sizeof(LZWStringTab) );
141 0 : for ( iCode = 0; iCode < 256; iCode++ )
142 0 : LZWUpdateTab( poCodeTab, NO_PRED, (char)iCode );
143 :
144 : // The first code is always known
145 0 : iCode = (*pabyIn++ << 4) & 0xFF0; nSizeIn--;
146 0 : iCode += (*pabyIn >> 4) & 0x00F;
147 0 : iOldCode = iCode;
148 0 : bBitsleft = TRUE;
149 :
150 0 : *pabyOut++ = iFinChar = poCodeTab[iCode].iFollower; nSizeOut--;
151 :
152 : // Decompress the input buffer
153 0 : while ( nSizeIn > 0 )
154 : {
155 : int bNewCode;
156 0 : GUInt32 nStackCount = 0;
157 : GByte abyStack[STACKSIZE];
158 0 : GByte *pabyTail = abyStack + STACKSIZE;
159 :
160 : // Fetch 12-bit code from input stream
161 0 : if ( bBitsleft )
162 : {
163 0 : iCode = ((*pabyIn++ & 0x0F) << 8) & 0xF00; nSizeIn--;
164 0 : if ( nSizeIn <= 0 )
165 0 : break;
166 0 : iCode += *pabyIn++; nSizeIn--;
167 0 : bBitsleft = FALSE;
168 : }
169 : else
170 : {
171 0 : iCode = (*pabyIn++ << 4) & 0xFF0; nSizeIn--;
172 0 : if ( nSizeIn <= 0 )
173 0 : break;
174 0 : iCode += (*pabyIn >> 4) & 0x00F;
175 0 : bBitsleft = TRUE;
176 : }
177 0 : iInCode = iCode;
178 :
179 : // Do we have unknown code?
180 0 : if ( poCodeTab[iCode].bUsed )
181 0 : bNewCode = FALSE;
182 : else
183 : {
184 0 : iCode = iOldCode;
185 0 : bLastChar = iFinChar;
186 0 : bNewCode = TRUE;
187 : }
188 :
189 0 : while ( poCodeTab[iCode].iPredecessor != NO_PRED )
190 : {
191 : // Stack overrun
192 0 : if ( nStackCount >= STACKSIZE )
193 0 : goto bad;
194 : // Put the decoded character into stack
195 0 : *(--pabyTail) = poCodeTab[iCode].iFollower; nStackCount++;
196 0 : iCode = poCodeTab[iCode].iPredecessor;
197 : }
198 :
199 0 : if ( !nSizeOut )
200 0 : goto bad;
201 : // The first character
202 0 : *pabyOut++ = iFinChar = poCodeTab[iCode].iFollower; nSizeOut--;
203 :
204 : // Output buffer overrun
205 0 : if ( nStackCount > nSizeOut )
206 0 : goto bad;
207 :
208 : // Now copy the stack contents into output buffer. Our stack was
209 : // filled in reverse order, so no need in character reordering
210 0 : memcpy( pabyOut, pabyTail, nStackCount );
211 0 : nSizeOut -= nStackCount;
212 0 : pabyOut += nStackCount;
213 :
214 : // If code isn't known
215 0 : if ( bNewCode )
216 : {
217 : // Output buffer overrun
218 0 : if ( !nSizeOut )
219 0 : goto bad;
220 0 : *pabyOut++ = iFinChar = bLastChar; // the follower char of last
221 0 : nSizeOut--;
222 : }
223 :
224 0 : if ( nCount > 0 )
225 : {
226 0 : nCount--;
227 : // Add code to the table
228 0 : LZWUpdateTab( poCodeTab, iOldCode, iFinChar );
229 : }
230 :
231 0 : iOldCode = iInCode;
232 : }
233 :
234 0 : CPLFree( poCodeTab );
235 0 : return 1;
236 :
237 : bad:
238 0 : CPLFree( poCodeTab );
239 0 : return 0;
240 : }
241 :
|
