home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / tools / chardir / ucmp8.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-19  |  11.0 KB  |  391 lines
  1.  
  2. /*
  3. ********************************************************************
  4. * COPYRIGHT: 
  5. * (C) Copyright Taligent, Inc., 1997
  6. * (C) Copyright International Business Machines Corporation, 1997 - 1998
  7. * Licensed Material - Program-Property of IBM - All Rights Reserved. 
  8. * US Government Users Restricted Rights - Use, duplication, or disclosure 
  9. * restricted by GSA ADP Schedule Contract with IBM Corp. 
  10. *
  11. ********************************************************************
  12. */
  13.  
  14. #ifndef _STDLIB_H
  15. #include <stdlib.h>
  16. #endif
  17.  
  18. #ifndef _STDIO_H
  19. #include <stdio.h>
  20. #endif
  21.  
  22.  
  23. #include "ucmp8.h"
  24. #include "cmemory.h"
  25.  
  26. static int32_t findOverlappingPosition(CompactByteArray* this,
  27.                        uint32_t start, 
  28.                        const UChar *tempIndex, 
  29.                        int32_t tempIndexCount, 
  30.                        uint32_t cycle);
  31.  
  32. /* internal constants*/
  33.  
  34. #define kUnicodeCount_int 65536
  35. #define kBlockShift_int 7
  36. #define kBlockCount_int (1<<kBlockShift_int)
  37. #define kIndexShift_int (16-kBlockShift_int)
  38. #define kIndexCount_int (1<<kIndexShift_int)
  39. #define kBlockMask_int (kBlockCount_int-1)
  40.  
  41. const int32_t UCMP8_kUnicodeCount = kUnicodeCount_int;
  42. const int32_t UCMP8_kBlockShift = kBlockShift_int;
  43. const int32_t UCMP8_kBlockCount = kBlockCount_int;
  44. const int32_t UCMP8_kIndexShift = kIndexShift_int;
  45. const int32_t UCMP8_kIndexCount = kIndexCount_int;
  46. const uint32_t UCMP8_kBlockMask = kBlockMask_int;
  47.  
  48.  
  49. int32_t ucmp8_getkUnicodeCount() { return UCMP8_kUnicodeCount;}
  50. int32_t ucmp8_getkBlockCount() { return UCMP8_kBlockCount;}
  51. int32_t ucmp8_getkIndexCount(){ return UCMP8_kIndexCount;}
  52. /* debug flags*/
  53. /*=======================================================*/
  54. U_CAPI int8_t ucmp8_get(CompactByteArray* array, uint16_t index) 
  55. {
  56.     return (array->fArray[(array->fIndex[index >> UCMP8_kBlockShift] & 0xFFFF) + (index & UCMP8_kBlockMask)]);
  57. }
  58. U_CAPI uint8_t ucmp8_getu(CompactByteArray* array, uint16_t index)
  59. {
  60.     return (uint8_t)ucmp8_get(array,index);
  61. }
  62.  
  63. CompactByteArray* ucmp8_open(int8_t defaultValue)
  64. {
  65. /* set up the index array and the data array.
  66.  * the index array always points into particular parts of the data array
  67.  * it is initially set up to point at regular block boundaries
  68.  * The following example uses blocks of 4 for simplicity
  69.  * Example: Expanded
  70.  * INDEX# 0   1   2   3   4
  71.  * INDEX  0   4   8   12  16 ...
  72.  * ARRAY  abcdeababcedzyabcdea...
  73.  *        |   |   |   |   |   |...
  74.  * whenever you set an element in the array, it unpacks to this state
  75.  * After compression, the index will point to various places in the data array
  76.  * wherever there is a runs of the same elements as in the original
  77.  * Example: Compressed
  78.  * INDEX# 0   1   2   3   4
  79.  * INDEX  0   4   1   8   2 ...
  80.  * ARRAY  abcdeabazyabc...
  81.  * If you look at the example, index# 2 in the expanded version points
  82.  * to data position number 8, which has elements "bced". In the compressed
  83.  * version, index# 2 points to data position 1, which also has "bced"
  84.  */
  85.   CompactByteArray* this = (CompactByteArray*) icu_malloc(sizeof(CompactByteArray));
  86.   int32_t i;
  87.   
  88.   if (this == NULL) return NULL;
  89.  
  90.   this->fArray = NULL; 
  91.   this->fIndex = NULL;
  92.   this->fCount = UCMP8_kUnicodeCount;
  93.   this->fCompact = FALSE; 
  94.   this->fBogus = FALSE;
  95.  
  96.  
  97.   this->fArray = (int8_t*) icu_malloc(sizeof(int8_t) * UCMP8_kUnicodeCount);
  98.   if (!this->fArray) 
  99.     {
  100.       this->fBogus = TRUE;
  101.       return NULL;
  102.     }
  103.   this->fIndex = (uint16_t*) icu_malloc(sizeof(uint16_t) * UCMP8_kIndexCount);
  104.   if (!this->fIndex) 
  105.     {
  106.       icu_free(this->fArray);
  107.       this->fArray = NULL;
  108.       this->fBogus = TRUE;
  109.       return NULL;
  110.     }
  111.   for (i = 0; i < UCMP8_kUnicodeCount; ++i) 
  112.     {
  113.       this->fArray[i] = defaultValue;
  114.     }
  115.   for (i = 0; i < UCMP8_kIndexCount; ++i) 
  116.     {
  117.       this->fIndex[i] = (uint16_t)(i << UCMP8_kBlockShift);
  118.     }
  119.  
  120.   return this;
  121. }
  122.  
  123. CompactByteArray* ucmp8_openAdopt(uint16_t *indexArray,
  124.                   int8_t *newValues,
  125.                   int32_t count)
  126. {
  127.   CompactByteArray* this = (CompactByteArray*) icu_malloc(sizeof(CompactByteArray));
  128.   if (!this) return NULL;
  129.   
  130.   this->fArray = NULL;
  131.   this->fIndex = NULL; 
  132.   this->fCount = count;
  133.   this->fBogus = FALSE;
  134.   
  135.   this->fArray = newValues;
  136.   this->fIndex = indexArray;
  137.   this->fCompact = (count < UCMP8_kUnicodeCount) ? TRUE : FALSE;
  138.  
  139.   return this;
  140. }
  141.  
  142. /*=======================================================*/
  143.  
  144. void ucmp8_close(CompactByteArray* this) 
  145. {
  146.   icu_free(this->fArray);
  147.   this->fArray = NULL;
  148.   icu_free(this->fIndex);
  149.   this->fIndex = NULL;
  150.   this->fCount = 0;
  151.   this->fCompact = FALSE;
  152.   icu_free(this);
  153. }
  154.  
  155.  
  156. /*=======================================================*/
  157.  
  158. void ucmp8_expand(CompactByteArray* this) 
  159. {
  160.   /* can optimize later.
  161.    * if we have to expand, then walk through the blocks instead of using Get
  162.    * this code unpacks the array by copying the blocks to the normalized position.
  163.    * Example: Compressed
  164.    * INDEX# 0   1   2   3   4
  165.    * INDEX  0   4   1   8   2 ...
  166.    * ARRAY  abcdeabazyabc...
  167.    *  turns into
  168.    * Example: Expanded
  169.    * INDEX# 0   1   2   3   4
  170.    * INDEX  0   4   8   12  16 ...
  171.    * ARRAY  abcdeababcedzyabcdea...
  172.    */
  173.   int32_t i;
  174.   if (this->fCompact) 
  175.     {
  176.       int8_t* tempArray;
  177.       tempArray = (int8_t*) icu_malloc(sizeof(int8_t) * UCMP8_kUnicodeCount);
  178.       if (!tempArray) 
  179.     {
  180.       this->fBogus = TRUE;
  181.       return;
  182.     }
  183.       for (i = 0; i < UCMP8_kUnicodeCount; ++i) 
  184.     {
  185.       tempArray[i] = ucmp8_get(this,(UChar)i);  /* HSYS : How expand?*/
  186.         }
  187.       for (i = 0; i < UCMP8_kIndexCount; ++i) 
  188.     {
  189.       this->fIndex[i] = (uint16_t)(i<< UCMP8_kBlockShift);
  190.         }
  191.       icu_free(this->fArray);
  192.       this->fArray = tempArray;
  193.       this->fCompact = FALSE;
  194.     }
  195. }
  196.  
  197.  
  198. /*=======================================================*/
  199. /* this->fArray:    an array to be overlapped
  200.  * start and count: specify the block to be overlapped
  201.  * tempIndex:   the overlapped array (actually indices back into inputContents)
  202.  * inputHash:   an index of hashes for tempIndex, where
  203.  *      inputHash[i] = XOR of values from i-count+1 to i
  204.  */
  205. int32_t
  206. findOverlappingPosition(CompactByteArray* this, 
  207.             uint32_t start,
  208.             const UChar* tempIndex,
  209.             int32_t tempIndexCount,
  210.             uint32_t cycle) 
  211. {
  212.   /* this is a utility routine for finding blocks that overlap.
  213.    * IMPORTANT: the cycle number is very important. Small cycles take a lot
  214.    * longer to work. In some cases, they may be able to get better compaction.
  215.    */
  216.     
  217.   int32_t i;
  218.   int32_t j;
  219.   int32_t currentCount;
  220.   
  221.   for (i = 0; i < tempIndexCount; i += cycle) 
  222.     {
  223.       currentCount = UCMP8_kBlockCount;
  224.       if (i + UCMP8_kBlockCount > tempIndexCount) 
  225.     {
  226.       currentCount = tempIndexCount - i;
  227.         } 
  228.       for (j = 0; j < currentCount; ++j) 
  229.     {
  230.       if (this->fArray[start + j] != this->fArray[tempIndex[i + j]]) break;
  231.         }
  232.       if (j == currentCount) break;
  233.     }
  234.   
  235.   return i;
  236. }
  237.  
  238. bool_t
  239. ucmp8_isBogus(const CompactByteArray* this)
  240. {
  241.   return this->fBogus;
  242. }
  243.  
  244. const int8_t*
  245. ucmp8_getArray(const CompactByteArray* this)
  246. {
  247.   return this->fArray;
  248. }
  249.  
  250. const uint16_t*
  251. ucmp8_getIndex(const CompactByteArray* this)
  252. {
  253.   return this->fIndex;
  254. }
  255.  
  256. int32_t 
  257. ucmp8_getCount(const CompactByteArray* this)
  258. {
  259.   return this->fCount;
  260. }
  261.  
  262.  
  263. void 
  264. ucmp8_set(CompactByteArray* this,
  265.       UChar c,
  266.       int8_t value)
  267. {
  268.   if (this->fCompact == TRUE) 
  269.     {
  270.       ucmp8_expand(this);
  271.       if (this->fBogus) return;
  272.     }
  273.   this->fArray[(int32_t)c] = value;
  274. }
  275.  
  276.  
  277. void 
  278. ucmp8_setRange(CompactByteArray* this,
  279.            UChar start,
  280.            UChar end,
  281.            int8_t value)
  282. {
  283.   int32_t i;
  284.   if (this->fCompact == TRUE) 
  285.     {
  286.       ucmp8_expand(this);
  287.       if (this->fBogus) return;
  288.     }
  289.   for (i = start; i <= end; ++i) 
  290.     {
  291.       this->fArray[i] = value;
  292.     }
  293. }
  294.  
  295.  
  296. /*=======================================================*/
  297.  
  298. void 
  299. ucmp8_compact(CompactByteArray* this,
  300.           uint32_t cycle) 
  301. {
  302.   if (!this->fCompact) 
  303.     {
  304.       /* this actually does the compaction.
  305.        * it walks throught the contents of the expanded array, finding the
  306.        * first block in the data that matches the contents of the current index.
  307.        * As it works, it keeps an updated pointer to the last position,
  308.        * so that it knows how big to make the final array
  309.        * If the matching succeeds, then the index will point into the data
  310.        * at some earlier position.
  311.        * If the matching fails, then last position pointer will be bumped,
  312.        * and the index will point to that last block of data.
  313.        */
  314.       UChar*    tempIndex;
  315.       int32_t     tempIndexCount;
  316.       int8_t*     tempArray;
  317.       int32_t     iBlock, iIndex;
  318.       
  319.       /* fix cycle, must be 0 < cycle <= blockcount*/
  320.       if (cycle < 0) cycle = 1;
  321.       else if (cycle > (uint32_t)UCMP8_kBlockCount) cycle = UCMP8_kBlockCount;
  322.       
  323.       /* make temp storage, larger than we need*/
  324.       tempIndex = (UChar*) icu_malloc(sizeof(UChar)* UCMP8_kUnicodeCount);
  325.       if (!tempIndex) 
  326.     {
  327.       this->fBogus = TRUE;
  328.       return;
  329.         }               
  330.       /* set up first block.*/
  331.       tempIndexCount = UCMP8_kBlockCount;
  332.       for (iIndex = 0; iIndex < UCMP8_kBlockCount; ++iIndex) 
  333.     {
  334.       tempIndex[iIndex] = (uint16_t)iIndex;
  335.         }; /* endfor (iIndex = 0; .....)*/
  336.       this->fIndex[0] = 0;
  337.       
  338.       /* for each successive block, find out its first position in the compacted array*/
  339.       for (iBlock = 1; iBlock < UCMP8_kIndexCount; ++iBlock) 
  340.     {
  341.       int32_t newCount, firstPosition, block;
  342.       block = iBlock << UCMP8_kBlockShift;
  343.       /*      if (debugSmall) if (block > debugSmallLimit) break;*/
  344.       firstPosition = findOverlappingPosition(this, 
  345.                           block,
  346.                           tempIndex,
  347.                           tempIndexCount,
  348.                           cycle);
  349.       
  350.       /* if not contained in the current list, copy the remainder
  351.        * invariant; cumulativeHash[iBlock] = XOR of values from iBlock-kBlockCount+1 to iBlock
  352.        * we do this by XORing out cumulativeHash[iBlock-kBlockCount]
  353.        */
  354.       newCount = firstPosition + UCMP8_kBlockCount;
  355.       if (newCount > tempIndexCount) 
  356.         {
  357.           for (iIndex = tempIndexCount; iIndex < newCount; ++iIndex) 
  358.         {
  359.           tempIndex[iIndex] = (uint16_t)(iIndex - firstPosition + block);
  360.         } /* endfor (iIndex = tempIndexCount....)*/
  361.                 tempIndexCount = newCount;
  362.             } /* endif (newCount > tempIndexCount)*/
  363.       this->fIndex[iBlock] = (uint16_t)firstPosition;
  364.         } /* endfor (iBlock = 1.....)*/
  365.       
  366.       /* now allocate and copy the items into the array*/
  367.       tempArray = (int8_t*) icu_malloc(tempIndexCount * sizeof(int8_t));
  368.       if (!tempArray) 
  369.     {
  370.       this->fBogus = TRUE;
  371.       icu_free(tempIndex);
  372.       return;
  373.         }
  374.       for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) 
  375.     {
  376.       tempArray[iIndex] = this->fArray[tempIndex[iIndex]];
  377.         }
  378.       icu_free(this->fArray);
  379.       this->fArray = tempArray;
  380.       this->fCount = tempIndexCount;
  381.       
  382.       
  383.       /* free up temp storage*/
  384.       icu_free(tempIndex);
  385.       this->fCompact = TRUE;
  386.     } /* endif (!this->fCompact)*/
  387. }
  388.  
  389.  
  390.  
  391.