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