home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / common / ucmp32.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-19  |  15.2 KB  |  443 lines
  1. /*
  2. *****************************************************************************************
  3. *                                                                                       *
  4. * COPYRIGHT:                                                                            *
  5. *   (C) Copyright Taligent, Inc.,  1997                                                 *
  6. *   (C) Copyright International Business Machines Corporation,  1999               *
  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.  *
  15.  * File cmpshrta.cpp
  16.  *
  17.  * Modification History:
  18.  *
  19.  *  Date        Name        Description
  20.  *  2/5/97      aliu        Added CompactIntArray streamIn and streamOut methods.
  21.  *  3/4/97      aliu        Tuned performance of CompactIntArray constructor,
  22.  *                          based on performance data indicating that this_obj was slow.
  23.  * 05/07/97     helena      Added isBogus()
  24.  * 04/26/99     Madhu       Ported to C for C Implementation
  25.  *===============================================================================
  26.  */
  27. #include "ucmp32.h"
  28. #include "cmemory.h"
  29. #include "filestrm.h"
  30. #include <stdlib.h>
  31.  
  32.  
  33.  
  34. static int32_t ucmp32_findOverlappingPosition(CompactIntArray* this_obj, uint32_t start, 
  35.                                 const UChar *tempIndex, 
  36.                                 int32_t tempIndexCount, 
  37.                                 uint32_t cycle);
  38.      
  39. /* internal constants*/
  40. #define UCMP32_kUnicodeCount_int  65536
  41. #define UCMP32_kBlockShift_int  7
  42. #define UCMP32_kBlockCount_int  (1<<UCMP32_kBlockShift_int)
  43. #define UCMP32_kIndexShift_int  16-UCMP32_kBlockShift_int
  44. #define UCMP32_kIndexCount_int  (1<<UCMP32_kIndexShift_int)
  45. #define UCMP32_kBlockMask_int   UCMP32_kBlockCount_int-1
  46.  
  47. const int32_t UCMP32_kUnicodeCount = UCMP32_kUnicodeCount_int;
  48. const int32_t UCMP32_kBlockShift = UCMP32_kBlockShift_int;
  49. const int32_t UCMP32_kBlockCount = UCMP32_kBlockCount_int;
  50. const int32_t UCMP32_kIndexShift = UCMP32_kIndexShift_int;
  51. const int32_t UCMP32_kIndexCount = UCMP32_kIndexCount_int;
  52. const uint32_t UCMP32_kBlockMask = UCMP32_kBlockMask_int;
  53.  
  54.  
  55.  
  56. static  bool_t debugSmall = FALSE;
  57. static  uint32_t debugSmallLimit = 30000;
  58.  
  59. /** debug flags
  60.   *=======================================================
  61.   */
  62.  
  63. int32_t ucmp32_getkUnicodeCount() { return UCMP32_kUnicodeCount;}
  64. int32_t ucmp32_getkBlockCount() { return UCMP32_kBlockCount;}
  65.  
  66. U_CAPI int32_t ucmp32_get(CompactIntArray* array, uint16_t index) 
  67. {
  68.     return (array->fArray[(array->fIndex[index >> UCMP32_kBlockShift]) +
  69.                                  (index & UCMP32_kBlockMask)]);
  70. }
  71. U_CAPI uint32_t ucmp32_getu(CompactIntArray* array, uint16_t index)
  72. {
  73. return (uint32_t)ucmp32_get(array, index);
  74. }
  75.  
  76. U_CAPI void ucmp32_streamIn(CompactIntArray* this_obj, FileStream* is)
  77. {
  78. int32_t  newCount, len;
  79. char c;
  80.     if (!T_FileStream_error(is))
  81.     {
  82.         
  83.         T_FileStream_read(is, &newCount, sizeof(newCount));
  84.         if (this_obj->fCount != newCount)
  85.         {
  86.             this_obj->fCount = newCount;
  87.             icu_free(this_obj->fArray);
  88.             this_obj->fArray = 0;
  89.             this_obj->fArray = (int32_t*)icu_malloc(this_obj->fCount * sizeof(int32_t));
  90.             if (!this_obj->fArray) {
  91.                 this_obj->fBogus = TRUE;
  92.                 return;
  93.             }
  94.         }
  95.         T_FileStream_read(is, this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
  96.         T_FileStream_read(is, &len, sizeof(len));
  97.         if (len == 0)
  98.         {
  99.             icu_free(this_obj->fIndex);
  100.             this_obj->fIndex = 0;
  101.         }
  102.         else if (len == UCMP32_kIndexCount)
  103.         {
  104.             if (this_obj->fIndex == 0) 
  105.                 this_obj->fIndex =(uint16_t*)icu_malloc(UCMP32_kIndexCount * sizeof(uint16_t));
  106.             if (!this_obj->fIndex) {
  107.                 this_obj->fBogus = TRUE;
  108.                 icu_free(this_obj->fArray);
  109.                 this_obj->fArray = 0;
  110.                 return;
  111.             }
  112.             T_FileStream_read(is, this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
  113.         }
  114.         else
  115.         {
  116.             this_obj->fBogus = TRUE;
  117.             return;
  118.         }
  119.         /* char instead of int8_t for Mac compilation*/
  120.         T_FileStream_read(is, (char*)&c, sizeof(c));
  121.         this_obj->fCompact = (c != 0);
  122.     }
  123. }
  124.  
  125. U_CAPI void ucmp32_streamOut(CompactIntArray* this_obj, FileStream* os)
  126. {
  127.     char c;
  128. if (!T_FileStream_error(os))
  129.     {
  130.         if (this_obj->fCount != 0 && this_obj->fArray != 0)
  131.         {
  132.             T_FileStream_write(os, &(this_obj->fCount), sizeof(this_obj->fCount));
  133.             T_FileStream_write(os, this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
  134.         }
  135.         else
  136.         {
  137.             int32_t  zero = 0;
  138.             T_FileStream_write(os, &zero, sizeof(zero));
  139.         }
  140.  
  141.         if (this_obj->fIndex == 0)
  142.         {
  143.             int32_t len = 0;
  144.             T_FileStream_write(os, &len, sizeof(len));
  145.         }
  146.         else
  147.         {
  148.             int32_t len = UCMP32_kIndexCount;
  149.             T_FileStream_write(os, &len, sizeof(len));
  150.             T_FileStream_write(os, this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
  151.         }
  152.         c = this_obj->fCompact ? 1 : 0;  /* char instead of int8_t for Mac compilation*/
  153.         T_FileStream_write(os, (const char*)&c, sizeof(c));
  154.     }
  155. }
  156.  
  157. CompactIntArray* ucmp32_open(int32_t defaultValue)
  158. {
  159.   uint16_t  i;
  160.   int32_t *p, *p_end;
  161.   uint16_t *q, *q_end;
  162.   CompactIntArray* this_obj = (CompactIntArray*) icu_malloc(sizeof(CompactIntArray));
  163.   if (this_obj == NULL) return NULL;
  164.   
  165.   this_obj->fCount = UCMP32_kUnicodeCount;
  166.   this_obj->fCompact = FALSE; 
  167.   this_obj->fBogus = FALSE;
  168.   this_obj->fArray = NULL;
  169.   this_obj->fIndex = NULL;
  170.   
  171. /*set up the index array and the data array.
  172.  * the index array always points into particular parts of the data array
  173.  * it is initially set up to point at regular block boundaries
  174.  * The following example uses blocks of 4 for simplicity
  175.  * Example: Expanded
  176.  * INDEX# 0   1   2   3   4
  177.  * INDEX  0   4   8   12  16 ...
  178.  * ARRAY  abcdeababcedzyabcdea...
  179.  *        |   |   |   |   |   |...
  180.  * whenever you set an element in the array, it unpacks to this_obj state
  181.  * After compression, the index will point to various places in the data array
  182.  * wherever there is a runs of the same elements as in the original
  183.  * Example: Compressed
  184.  * INDEX# 0   1   2   3   4
  185.  * INDEX  0   4   1   8   2 ...
  186.  * ARRAY  abcdeabazyabc...
  187.  * If you look at the example, index# 2 in the expanded version points
  188.  * to data position number 8, which has elements "bced". In the compressed
  189.  * version, index# 2 points to data position 1, which also has "bced"
  190.  */
  191.     this_obj->fArray = (int32_t*)icu_malloc(UCMP32_kUnicodeCount * sizeof(int32_t));
  192.       if (this_obj->fArray == NULL)    {
  193.       this_obj->fBogus = TRUE;
  194.       return NULL;
  195.     }
  196.   
  197.     this_obj->fIndex = (uint16_t*)icu_malloc(UCMP32_kIndexCount * sizeof(uint16_t));
  198.     if (!this_obj->fIndex) {
  199.         icu_free(this_obj->fArray);
  200.         this_obj->fArray = NULL;
  201.         this_obj->fBogus = TRUE;
  202.         return NULL;
  203.     }
  204.     p = this_obj->fArray;
  205.     p_end = p + UCMP32_kUnicodeCount;
  206.     while (p < p_end) *p++ = defaultValue;
  207.  
  208.     q = this_obj->fIndex;
  209.     q_end = q + UCMP32_kIndexCount;
  210.     i = 0;
  211.     while (q < q_end)
  212.     {
  213.         *q++ = i;
  214.         i += (1 << UCMP32_kBlockShift);
  215.     }
  216.     return this_obj;
  217. }
  218.  
  219. CompactIntArray* ucmp32_openAdopt(uint16_t *indexArray, int32_t *newValues, int32_t  count)
  220. {
  221.   CompactIntArray* this_obj = (CompactIntArray*) icu_malloc(sizeof(CompactIntArray));
  222.   if (this_obj == NULL) return NULL;
  223.   this_obj->fCount = count; 
  224.   this_obj->fBogus = FALSE;
  225.   this_obj->fArray = newValues;
  226.   this_obj->fIndex = indexArray;
  227.   this_obj->fCompact = (count < UCMP32_kUnicodeCount) ? TRUE : FALSE;
  228.   return this_obj;
  229. }
  230.  
  231. /*=======================================================*/
  232.  
  233. void ucmp32_close(    CompactIntArray* this_obj) 
  234. {
  235.     icu_free(this_obj->fArray);
  236.     this_obj->fArray = NULL;
  237.     icu_free(this_obj->fIndex);
  238.     this_obj->fIndex = NULL;
  239.     this_obj->fCount = 0;
  240.     this_obj->fCompact = FALSE;
  241. }
  242.  
  243. bool_t ucmp32_isBogus(const CompactIntArray* this_obj)
  244. {
  245.     return this_obj->fBogus;
  246. }
  247.  
  248. void ucmp32_expand(CompactIntArray* this_obj) {
  249. /* can optimize later.
  250.  * if we have to expand, then walk through the blocks instead of using Get
  251.  * this_obj code unpacks the array by copying the blocks to the normalized position.
  252.  * Example: Compressed
  253.  * INDEX# 0   1   2   3   4
  254.  * INDEX  0   4   1   8   2 ...
  255.  * ARRAY  abcdeabazyabc...
  256.  *  turns into
  257.  * Example: Expanded
  258.  * INDEX# 0   1   2   3   4
  259.  * INDEX  0   4   8   12  16 ...
  260.  * ARRAY  abcdeababcedzyabcdea...
  261.  */
  262.     int32_t i;
  263.     int32_t* tempArray;
  264.     if (this_obj->fCompact) {
  265.         tempArray = (int32_t*)icu_malloc(UCMP32_kUnicodeCount * sizeof(int32_t));
  266.         if (tempArray == NULL) {
  267.             this_obj->fBogus = TRUE;
  268.             return;
  269.         }
  270.         for (i = 0; i < UCMP32_kUnicodeCount; ++i) {
  271.             tempArray[i] = ucmp32_get(this_obj, (UChar)i);  /* HSYS : How expand?*/
  272.         }
  273.         for (i = 0; i < UCMP32_kIndexCount; ++i) {
  274.             this_obj->fIndex[i] = (uint16_t)(i<<UCMP32_kBlockShift);
  275.         }
  276.         icu_free(this_obj->fArray);
  277.         this_obj->fArray = tempArray;
  278.         this_obj->fCompact = FALSE;
  279.     }
  280. }
  281.  
  282. uint32_t ucmp32_getCount(const CompactIntArray* this_obj)
  283. {
  284.     return this_obj->fCount;
  285. }
  286.  
  287. const int32_t* ucmp32_getArray(const CompactIntArray* this_obj)
  288. {
  289.     return this_obj->fArray;
  290. }
  291.  
  292. const uint16_t* ucmp32_getIndex(const CompactIntArray* this_obj)
  293. {
  294.     return this_obj->fIndex;
  295. }
  296.  
  297. void  ucmp32_set(CompactIntArray* this_obj, UChar c, int32_t value)
  298. {
  299.     if (this_obj->fCompact == TRUE) {
  300.         ucmp32_expand(this_obj);
  301.         if (this_obj->fBogus) return;
  302.     }
  303.     this_obj->fArray[(int32_t)c] = value;
  304. }
  305.  
  306.  
  307. void ucmp32_setRange(CompactIntArray* this_obj, UChar start, UChar end, int32_t value)
  308. {
  309.     int32_t i;
  310.     if (this_obj->fCompact == TRUE) {
  311.         ucmp32_expand(this_obj);
  312.         if (this_obj->fBogus) return;
  313.  
  314.     }
  315.     for (i = start; i <= end; ++i) {
  316.         this_obj->fArray[i] = value;
  317.     }
  318. }
  319. /*=======================================================
  320.  * this_obj->fArray:    an array to be overlapped
  321.  * start and count: specify the block to be overlapped
  322.  * tempIndex:   the overlapped array (actually indices back into inputContents)
  323.  * inputHash:   an index of hashes for tempIndex, where
  324.  *      inputHash[i] = XOR of values from i-count+1 to i
  325.  */
  326.  
  327. int32_t ucmp32_findOverlappingPosition(CompactIntArray* this_obj, 
  328.                     uint32_t  start,
  329.                     const UChar* tempIndex,
  330.                     int32_t  tempIndexCount,
  331.                     uint32_t  cycle) {
  332. /* this_obj is a utility routine for finding blocks that overlap.
  333.  * IMPORTANT: the cycle number is very important. Small cycles take a lot
  334.  * longer to work. In some cases, they may be able to get better compaction.
  335.  */
  336.     int32_t  i;
  337.     int32_t  j;
  338.     int32_t  currentCount;
  339.         
  340.  
  341.     for (i = 0; i < tempIndexCount; i += cycle) {
  342.         currentCount = UCMP32_kBlockCount;
  343.         if (i + UCMP32_kBlockCount > tempIndexCount) {
  344.             currentCount = tempIndexCount - i;
  345.         } 
  346.         for (j = 0; j < currentCount; ++j) {
  347.             if (this_obj->fArray[start + j] != this_obj->fArray[tempIndex[i + j]]) break;
  348.         }
  349.         if (j == currentCount) break;
  350.     }
  351.  
  352.     return i;
  353. }
  354. /*=======================================================*/
  355.  
  356. void ucmp32_compact(CompactIntArray* this_obj, int32_t cycle) {
  357. /* this_obj actually does the compaction.
  358.  * it walks throught the contents of the expanded array, finding the
  359.  * first block in the data that matches the contents of the current index.
  360.  * As it works, it keeps an updated pointer to the last position,
  361.  * so that it knows how big to make the final array
  362.  * If the matching succeeds, then the index will point into the data
  363.  * at some earlier position.
  364.  * If the matching fails, then last position pointer will be bumped,
  365.  * and the index will point to that last block of data.
  366.  */
  367.    UChar* tempIndex;
  368.    int32_t  tempIndexCount;
  369.    int32_t* tempArray;
  370.    int32_t  iBlock, iIndex;
  371.    int32_t newCount, firstPosition;
  372.    uint32_t block;
  373.     if (!this_obj->fCompact) {
  374.                 
  375.         /* fix cycle, must be 0 < cycle <= blockcount*/
  376.         if (cycle < 0) cycle = 1;
  377.         else if (cycle > UCMP32_kBlockCount)
  378.             cycle = UCMP32_kBlockCount;
  379.  
  380.         /* make temp storage, larger than we need*/
  381.         tempIndex =(UChar*)icu_malloc(UCMP32_kUnicodeCount * sizeof(uint32_t));
  382.         if (tempIndex == NULL) {
  383.             this_obj->fBogus = TRUE;
  384.             return;
  385.         }               
  386.         /* set up first block.*/
  387.         tempIndexCount = UCMP32_kBlockCount;
  388.         for (iIndex = 0; iIndex < UCMP32_kBlockCount; ++iIndex) {
  389.             tempIndex[iIndex] = (uint16_t)iIndex;
  390.         }; /* endfor (iIndex = 0; .....)*/
  391.         this_obj->fIndex[0] = 0;
  392.     
  393.     /* for each successive block, find out its first position in the compacted array*/
  394.         for (iBlock = 1; iBlock < UCMP32_kIndexCount; ++iBlock) {
  395.             
  396.             block = iBlock<<UCMP32_kBlockShift;
  397.             if (debugSmall) if (block > debugSmallLimit) break;
  398.             firstPosition = ucmp32_findOverlappingPosition(this_obj, block, tempIndex, tempIndexCount, cycle);
  399.             
  400.         /* if not contained in the current list, copy the remainder
  401.          * invariant; cumulativeHash[iBlock] = XOR of values from iBlock-kBlockCount+1 to iBlock
  402.          * we do this_obj by XORing out cumulativeHash[iBlock-kBlockCount]
  403.          */
  404.             newCount = firstPosition + UCMP32_kBlockCount;
  405.             if (newCount > tempIndexCount) {
  406.                 for (iIndex = tempIndexCount; iIndex < newCount; ++iIndex) {
  407.                     tempIndex[iIndex] = (uint16_t)(iIndex - firstPosition + block);
  408.                 } /* endfor (iIndex = tempIndexCount....)*/
  409.                 tempIndexCount = newCount;
  410.             } /*endif (newCount > tempIndexCount)*/
  411.             this_obj->fIndex[iBlock] = (uint16_t)firstPosition;
  412.         } /* endfor (iBlock = 1.....)*/
  413.         
  414.  
  415.         
  416.     /* now allocate and copy the items into the array*/
  417.         tempArray = (int32_t*)icu_malloc(tempIndexCount * sizeof(uint32_t));
  418.         if (tempArray == NULL) {
  419.             this_obj->fBogus = TRUE;
  420.             icu_free(tempIndex);
  421.             return;
  422.         }
  423.         for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  424.             tempArray[iIndex] = this_obj->fArray[tempIndex[iIndex]];
  425.         }
  426.         icu_free(this_obj->fArray);
  427.         this_obj->fArray = tempArray;
  428.         this_obj->fCount = tempIndexCount;
  429.     
  430.  
  431.     
  432.     /* free up temp storage*/
  433.         icu_free(tempIndex);
  434.         this_obj->fCompact = TRUE;
  435.  
  436. #ifdef _DEBUG
  437.         /*the following line is useful for specific debugging purposes*/
  438.         /*fprintf(stderr, "Compacted to %ld with cycle %d\n", fCount, cycle);*/
  439. #endif
  440.     } /* endif (!this_obj->fCompact)*/
  441. }
  442.  
  443.