Line data    Source code

       1             : /******************************************************************************
       2             :  *
       3             :  * Project:  Raster Matrix Format
       4             :  * Purpose:  Implementation of the LZW compression algorithm as used in
       5             :  *           GIS "Panorama"/"Integratsia" raster files. Based on implementation
       6             :  *           of Kent Williams, but heavily modified over it. The key point
       7             :  *           in the initial implementation is a hashing algorithm.
       8             :  * Author:   Andrey Kiselev, dron@ak4719.spb.edu
       9             :  *
      10             :  ******************************************************************************
      11             :  * Copyright (c) 2007, Andrey Kiselev <dron@ak4719.spb.edu>
      12             :  *
      13             :  * SPDX-License-Identifier: MIT
      14             :  ******************************************************************************
      15             :  * COPYRIGHT NOTICE FROM THE INITIAL IMPLEMENTATION:
      16             :  *
      17             :  * The programs LZWCOM and LZWUNC, both in binary executable and source forms,
      18             :  * are in the public domain.  No warranty is given or implied, and no
      19             :  * liability will be assumed by the author.
      20             :  *
      21             :  * Everyone on earth is hereby given permission to use, copy, distribute,
      22             :  * change, mangle, destroy or otherwise employ these programs, provided they
      23             :  * hurt no one but themselves in the process.
      24             :  *
      25             :  * Kent Williams
      26             :  * Norand Inc.
      27             :  * 550 2nd St S.E.
      28             :  * Cedar Rapids, Iowa 52401
      29             :  * (319) 369-3131
      30             :  ****************************************************************************/
      31             : 
      32             : #include "cpl_conv.h"
      33             : 
      34             : #include "rmfdataset.h"
      35             : 
      36             : // Code marks that there is no predecessor in the string
      37             : constexpr GUInt32 NO_PRED = 0xFFFF;
      38             : 
      39             : // We are using 12-bit codes in this particular implementation
      40             : constexpr GUInt32 TABSIZE = 4096U;
      41             : constexpr GUInt32 STACKSIZE = TABSIZE;
      42             : 
      43             : constexpr GUInt32 NOT_FND = 0xFFFF;
      44             : 
      45             : /************************************************************************/
      46             : /*                           LZWStringTab                               */
      47             : /************************************************************************/
      48             : 
      49             : typedef struct
      50             : {
      51             :     bool bUsed;
      52             :     GUInt32 iNext;         // hi bit is 'used' flag
      53             :     GUInt32 iPredecessor;  // 12 bit code
      54             :     GByte iFollower;
      55             : } LZWStringTab;
      56             : 
      57             : /************************************************************************/
      58             : /*                           LZWUpdateTab()                             */
      59             : /************************************************************************/
      60             : 
      61             : CPL_NOSANITIZE_UNSIGNED_INT_OVERFLOW
      62    18549300 : static GUInt32 UnsanitizedMul(GUInt32 a, GUInt32 b)
      63             : {
      64    18549300 :     return a * b;
      65             : }
      66             : 
      67    18605600 : static int UnsignedByteToSignedByte(GByte byVal)
      68             : {
      69    18605600 :     return byVal >= 128 ? byVal - 256 : byVal;
      70             : }
      71             : 
      72      980284 : static void LZWUpdateTab(LZWStringTab *poCodeTab, GUInt32 iPred, GByte bFollow)
      73             : {
      74             :     /* -------------------------------------------------------------------- */
      75             :     /* Hash uses the 'mid-square' algorithm. I.E. for a hash val of n bits  */
      76             :     /* hash = middle binary digits of (key * key).  Upon collision, hash    */
      77             :     /* searches down linked list of keys that hashed to that key already.   */
      78             :     /* It will NOT notice if the table is full. This must be handled        */
      79             :     /* elsewhere                                                            */
      80             :     /* -------------------------------------------------------------------- */
      81      980284 :     const int iFollow = UnsignedByteToSignedByte(bFollow);
      82      980684 :     GUInt32 nLocal = CPLUnsanitizedAdd<GUInt32>(iPred, iFollow) | 0x0800;
      83      980593 :     nLocal = (UnsanitizedMul(nLocal, nLocal) >> 6) &
      84             :              0x0FFF;  // middle 12 bits of result
      85             : 
      86             :     // If string is not used
      87      980423 :     GUInt32 nNext = nLocal;
      88      980423 :     if (poCodeTab[nLocal].bUsed)
      89             :     {
      90             :         // If collision has occurred
      91     1917960 :         while ((nNext = poCodeTab[nLocal].iNext) != 0)
      92     1255520 :             nLocal = nNext;
      93             : 
      94             :         // Search for free entry from nLocal + 101
      95      662440 :         nNext = (nLocal + 101) & 0x0FFF;
      96    34132200 :         while (poCodeTab[nNext].bUsed)
      97             :         {
      98    33469700 :             if (++nNext >= TABSIZE)
      99        2788 :                 nNext = 0;
     100             :         }
     101             : 
     102             :         // Put new tempnext into last element in collision list
     103      662440 :         poCodeTab[nLocal].iNext = nNext;
     104             :     }
     105             : 
     106      980423 :     poCodeTab[nNext].bUsed = true;
     107      980423 :     poCodeTab[nNext].iNext = 0;
     108      980423 :     poCodeTab[nNext].iPredecessor = iPred;
     109      980423 :     poCodeTab[nNext].iFollower = bFollow;
     110      980423 : }
     111             : 
     112             : /************************************************************************/
     113             : /*                           LZWCreateTab()                             */
     114             : /************************************************************************/
     115             : 
     116         261 : static LZWStringTab *LZWCreateTab()
     117             : {
     118             :     // Allocate space for the new table and pre-fill it
     119             :     LZWStringTab *poCodeTab =
     120         261 :         (LZWStringTab *)CPLMalloc(TABSIZE * sizeof(LZWStringTab));
     121             : 
     122         261 :     memset(poCodeTab, 0, TABSIZE * sizeof(LZWStringTab));
     123             : 
     124       67077 :     for (GUInt32 iCode = 0; iCode < 256; ++iCode)
     125       66816 :         LZWUpdateTab(poCodeTab, NO_PRED, static_cast<GByte>(iCode));
     126             : 
     127         261 :     return poCodeTab;
     128             : }
     129             : 
     130             : /************************************************************************/
     131             : /*                            LZWFindIndex()                            */
     132             : /************************************************************************/
     133             : 
     134    17467600 : static GUInt32 LZWFindIndex(const LZWStringTab *poCodeTab, GUInt32 iPred,
     135             :                             GByte bFollow)
     136             : {
     137    17467600 :     const int iFollow = UnsignedByteToSignedByte(bFollow);
     138    17518200 :     GUInt32 nLocal = CPLUnsanitizedAdd<GUInt32>(iPred, iFollow) | 0x0800;
     139    17459500 :     nLocal = (UnsanitizedMul(nLocal, nLocal) >> 6) &
     140             :              0x0FFF;  // middle 12 bits of result
     141             : 
     142    25350700 :     do
     143             :     {
     144    36803800 :         CPLAssert(nLocal < TABSIZE);
     145    36803800 :         if (poCodeTab[nLocal].iPredecessor == iPred &&
     146    14284200 :             poCodeTab[nLocal].iFollower == bFollow)
     147             :         {
     148    14207600 :             return nLocal;
     149             :         }
     150    22596100 :         nLocal = poCodeTab[nLocal].iNext;
     151    22596100 :     } while (nLocal > 0);
     152             : 
     153           0 :     return NOT_FND;
     154             : }
     155             : 
     156             : /************************************************************************/
     157             : /*                             LZWPutCode()                             */
     158             : /************************************************************************/
     159             : 
     160     5097510 : static bool LZWPutCode(GUInt32 iCode, GUInt32 &iTmp, bool &bBitsleft,
     161             :                        GByte *&pabyCurrent, const GByte *const pabyOutEnd)
     162             : {
     163     5097510 :     if (bBitsleft)
     164             :     {
     165     2587710 :         if (pabyCurrent >= pabyOutEnd)
     166             :         {
     167           0 :             return false;
     168             :         }
     169     2587710 :         *(pabyCurrent++) = static_cast<GByte>((iCode >> 4) & 0xFF);
     170     2587710 :         iTmp = iCode & 0x000F;
     171     2587710 :         bBitsleft = false;
     172             :     }
     173             :     else
     174             :     {
     175     2509800 :         if (pabyCurrent + 1 >= pabyOutEnd)
     176             :         {
     177          28 :             return false;
     178             :         }
     179     2509770 :         *(pabyCurrent++) =
     180     2509770 :             static_cast<GByte>(((iTmp << 4) & 0xFF0) + ((iCode >> 8) & 0x00F));
     181     2509770 :         *(pabyCurrent++) = static_cast<GByte>(iCode & 0xFF);
     182     2509770 :         bBitsleft = true;
     183             :     }
     184     5097480 :     return true;
     185             : }
     186             : 
     187             : /************************************************************************/
     188             : /*                           LZWReadStream()                            */
     189             : /************************************************************************/
     190             : 
     191         137 : static size_t LZWReadStream(const GByte *pabyIn, GUInt32 nSizeIn,
     192             :                             GByte *pabyOut, GUInt32 nSizeOut,
     193             :                             LZWStringTab *poCodeTab)
     194             : {
     195         137 :     GByte *const pabyOutBegin = pabyOut;
     196             : 
     197             :     // The first code is always known
     198         137 :     GUInt32 iCode = (*pabyIn++ << 4) & 0xFF0;
     199         137 :     nSizeIn--;
     200         137 :     iCode += (*pabyIn >> 4) & 0x00F;
     201         137 :     GUInt32 iOldCode = iCode;
     202         137 :     bool bBitsleft = true;
     203             : 
     204         137 :     GByte iFinChar = poCodeTab[iCode].iFollower;
     205         137 :     nSizeOut--;
     206         137 :     *pabyOut++ = iFinChar;
     207             : 
     208         137 :     GUInt32 nCount = TABSIZE - 256;
     209             : 
     210             :     // Decompress the input buffer
     211     4783380 :     while (nSizeIn > 0)
     212             :     {
     213             :         // Fetch 12-bit code from input stream
     214     4783300 :         if (bBitsleft)
     215             :         {
     216     2391720 :             iCode = ((*pabyIn++ & 0x0F) << 8) & 0xF00;
     217     2391720 :             nSizeIn--;
     218     2391720 :             if (nSizeIn == 0)
     219          57 :                 break;
     220     2391660 :             iCode += *pabyIn++;
     221     2391660 :             nSizeIn--;
     222     2391660 :             bBitsleft = FALSE;
     223             :         }
     224             :         else
     225             :         {
     226     2391580 :             iCode = (*pabyIn++ << 4) & 0xFF0;
     227     2391580 :             nSizeIn--;
     228     2391580 :             if (nSizeIn == 0)
     229           0 :                 break;
     230     2391580 :             iCode += (*pabyIn >> 4) & 0x00F;
     231     2391580 :             bBitsleft = TRUE;
     232             :         }
     233             : 
     234     4783250 :         const GUInt32 iInCode = iCode;
     235     4783250 :         GByte bLastChar = 0;  // TODO(schwehr): Why not nLastChar?
     236             : 
     237             :         // Do we have unknown code?
     238     4783250 :         bool bNewCode = false;
     239     4783250 :         if (!poCodeTab[iCode].bUsed)
     240             :         {
     241       40101 :             iCode = iOldCode;
     242       40101 :             bLastChar = iFinChar;
     243       40101 :             bNewCode = true;
     244             :         }
     245             : 
     246     4783250 :         GByte abyStack[STACKSIZE] = {};
     247     4783250 :         GByte *pabyTail = abyStack + STACKSIZE;
     248     4783250 :         GUInt32 nStackCount = 0;
     249             : 
     250    16371000 :         while (poCodeTab[iCode].iPredecessor != NO_PRED)
     251             :         {
     252             :             // Stack overrun
     253    11587700 :             if (nStackCount >= STACKSIZE)
     254           0 :                 return 0;
     255             :             // Put the decoded character into stack
     256    11587700 :             *(--pabyTail) = poCodeTab[iCode].iFollower;
     257    11587700 :             nStackCount++;
     258    11587700 :             iCode = poCodeTab[iCode].iPredecessor;
     259             :         }
     260             : 
     261     4783250 :         if (!nSizeOut)
     262           0 :             return 0;
     263             :         // The first character
     264     4783250 :         iFinChar = poCodeTab[iCode].iFollower;
     265     4783250 :         nSizeOut--;
     266     4783250 :         *pabyOut++ = iFinChar;
     267             : 
     268             :         // Output buffer overrun
     269     4783250 :         if (nStackCount > nSizeOut)
     270           0 :             return 0;
     271             : 
     272             :         // Now copy the stack contents into output buffer. Our stack was
     273             :         // filled in reverse order, so no need in character reordering
     274     4783250 :         memcpy(pabyOut, pabyTail, nStackCount);
     275     4783250 :         nSizeOut -= nStackCount;
     276     4783250 :         pabyOut += nStackCount;
     277             : 
     278             :         // If code isn't known
     279     4783250 :         if (bNewCode)
     280             :         {
     281             :             // Output buffer overrun
     282       40101 :             if (!nSizeOut)
     283           0 :                 return 0;
     284       40101 :             iFinChar = bLastChar;  // the follower char of last
     285       40101 :             *pabyOut++ = iFinChar;
     286       40101 :             nSizeOut--;
     287             :         }
     288             : 
     289     4783250 :         if (nCount > 0)
     290             :         {
     291      463213 :             nCount--;
     292             :             // Add code to the table
     293      463213 :             LZWUpdateTab(poCodeTab, iOldCode, iFinChar);
     294             :         }
     295             : 
     296     4783250 :         iOldCode = iInCode;
     297             :     }
     298             : 
     299         137 :     return static_cast<size_t>(pabyOut - pabyOutBegin);
     300             : }
     301             : 
     302             : /************************************************************************/
     303             : /*                           LZWDecompress()                            */
     304             : /************************************************************************/
     305             : 
     306         137 : size_t RMFDataset::LZWDecompress(const GByte *pabyIn, GUInt32 nSizeIn,
     307             :                                  GByte *pabyOut, GUInt32 nSizeOut, GUInt32,
     308             :                                  GUInt32)
     309             : {
     310         137 :     if (pabyIn == nullptr || pabyOut == nullptr || nSizeIn < 2)
     311           0 :         return 0;
     312         137 :     LZWStringTab *poCodeTab = LZWCreateTab();
     313             : 
     314         137 :     size_t nRet = LZWReadStream(pabyIn, nSizeIn, pabyOut, nSizeOut, poCodeTab);
     315             : 
     316         137 :     CPLFree(poCodeTab);
     317             : 
     318         137 :     return nRet;
     319             : }
     320             : 
     321             : /************************************************************************/
     322             : /*                             LZWWriteStream()                         */
     323             : /************************************************************************/
     324             : 
     325         124 : static size_t LZWWriteStream(const GByte *pabyIn, GUInt32 nSizeIn,
     326             :                              GByte *pabyOut, GUInt32 nSizeOut,
     327             :                              LZWStringTab *poCodeTab)
     328             : {
     329             :     GUInt32 iCode;
     330         124 :     iCode = LZWFindIndex(poCodeTab, NO_PRED, *pabyIn++);
     331         124 :     nSizeIn--;
     332             : 
     333         124 :     GUInt32 nCount = TABSIZE - 256;
     334         124 :     GUInt32 iTmp = 0;
     335         124 :     bool bBitsleft = true;
     336         124 :     GByte *pabyCurrent = pabyOut;
     337         124 :     GByte *pabyOutEnd = pabyOut + nSizeOut;
     338             : 
     339    14078000 :     while (nSizeIn > 0)
     340             :     {
     341    14077900 :         const GByte bCurrentCode = *pabyIn++;
     342    14077900 :         nSizeIn--;
     343             : 
     344    14077900 :         GUInt32 iNextCode = LZWFindIndex(poCodeTab, iCode, bCurrentCode);
     345    13753800 :         if (iNextCode != NOT_FND)
     346             :         {
     347     9861850 :             iCode = iNextCode;
     348     9861850 :             continue;
     349             :         }
     350             : 
     351     3891910 :         if (!LZWPutCode(iCode, iTmp, bBitsleft, pabyCurrent, pabyOutEnd))
     352             :         {
     353          28 :             return 0;
     354             :         }
     355             : 
     356     5151160 :         if (nCount > 0)
     357             :         {
     358      450443 :             nCount--;
     359      450443 :             LZWUpdateTab(poCodeTab, iCode, bCurrentCode);
     360             :         }
     361             : 
     362     5152530 :         iCode = LZWFindIndex(poCodeTab, NO_PRED, bCurrentCode);
     363             :     }
     364             : 
     365          96 :     if (!LZWPutCode(iCode, iTmp, bBitsleft, pabyCurrent, pabyOutEnd))
     366             :     {
     367           0 :         return 0;
     368             :     }
     369             : 
     370          96 :     if (!bBitsleft)
     371             :     {
     372          52 :         if (pabyCurrent >= pabyOutEnd)
     373             :         {
     374           0 :             return 0;
     375             :         }
     376          52 :         *(pabyCurrent++) = static_cast<GByte>((iTmp << 4) & 0xFF0);
     377             :     }
     378             : 
     379          96 :     return static_cast<size_t>(pabyCurrent - pabyOut);
     380             : }
     381             : 
     382             : /************************************************************************/
     383             : /*                             LZWCompress()                            */
     384             : /************************************************************************/
     385             : 
     386         124 : size_t RMFDataset::LZWCompress(const GByte *pabyIn, GUInt32 nSizeIn,
     387             :                                GByte *pabyOut, GUInt32 nSizeOut, GUInt32,
     388             :                                GUInt32, const RMFDataset *)
     389             : {
     390         124 :     if (pabyIn == nullptr || pabyOut == nullptr || nSizeIn == 0)
     391           0 :         return 0;
     392             : 
     393             :     // Allocate space for the new table and pre-fill it
     394         124 :     LZWStringTab *poCodeTab = LZWCreateTab();
     395             : 
     396             :     size_t nWritten =
     397         124 :         LZWWriteStream(pabyIn, nSizeIn, pabyOut, nSizeOut, poCodeTab);
     398             : 
     399         124 :     CPLFree(poCodeTab);
     400             : 
     401         124 :     return nWritten;
     402             : }