/*============================================================================
 * Copyright (C) 1997-1999, International Business Machines Corporation
 * and others. All Rights Reserved.
 *
 * File cmpshrta.cpp
 *
 * Modification History:
 *
 *  Date        Name        Description
 *  2/5/97      aliu        Added CompactIntArray streamIn and streamOut methods.
 *  3/4/97      aliu        Tuned performance of CompactIntArray constructor,
 *                          based on performance data indicating that this_obj was slow.
 * 05/07/97     helena      Added isBogus()
 * 04/26/99     Madhu       Ported to C for C Implementation
 * 11/12/99     srl         macroized ucmp32_get()
 * 11/07/00     weiv        aligned implementation with ucmp8
 *===============================================================================
 */
#include "ucmp32.h"
#include "cmemory.h"
#include "filestrm.h"
#include <stdlib.h>


static int32_t ucmp32_findOverlappingPosition(CompactIntArray* this_obj, uint32_t start, 
                                const UChar *tempIndex, 
                                int32_t tempIndexCount, 
                                uint32_t cycle);

static  UBool debugSmall = FALSE;
static  uint32_t debugSmallLimit = 30000;

/** debug flags
  *=======================================================
  */

int32_t ucmp32_getkUnicodeCount() { return UCMP32_kUnicodeCount;}
int32_t ucmp32_getkBlockCount() { return UCMP32_kBlockCount;}

U_CAPI void ucmp32_streamIn(CompactIntArray* this_obj, FileStream* is)
{
int32_t  newCount, len;
char c;
    if (!T_FileStream_error(is))
    {
        
        T_FileStream_read(is, &newCount, sizeof(newCount));
        if (this_obj->fCount != newCount)
        {
            this_obj->fCount = newCount;
            uprv_free(this_obj->fArray);
            this_obj->fArray = 0;
            this_obj->fArray = (int32_t*)uprv_malloc(this_obj->fCount * sizeof(int32_t));
            if (!this_obj->fArray) {
                this_obj->fBogus = TRUE;
                return;
            }
        }
        T_FileStream_read(is, this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
        T_FileStream_read(is, &len, sizeof(len));
        if (len == 0)
        {
            uprv_free(this_obj->fIndex);
            this_obj->fIndex = 0;
        }
        else if (len == UCMP32_kIndexCount)
        {
            if (this_obj->fIndex == 0) 
                this_obj->fIndex =(uint16_t*)uprv_malloc(UCMP32_kIndexCount * sizeof(uint16_t));
            if (!this_obj->fIndex) {
                this_obj->fBogus = TRUE;
                uprv_free(this_obj->fArray); 
                this_obj->fArray = 0;
                return;
            }
            T_FileStream_read(is, this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
        }
        else
        {
            this_obj->fBogus = TRUE;
            return;
        }
        /* char instead of int8_t for Mac compilation*/
        T_FileStream_read(is, (char*)&c, sizeof(c));
        this_obj->fCompact = (UBool)(c != 0);
    }
}

U_CAPI void ucmp32_streamOut(CompactIntArray* this_obj, FileStream* os)
{
    char c;
if (!T_FileStream_error(os))
    {
        if (this_obj->fCount != 0 && this_obj->fArray != 0)
        {
            T_FileStream_write(os, &(this_obj->fCount), sizeof(this_obj->fCount));
            T_FileStream_write(os, this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
        }
        else
        {
            int32_t  zero = 0;
            T_FileStream_write(os, &zero, sizeof(zero));
        }

        if (this_obj->fIndex == 0)
        {
            int32_t len = 0;
            T_FileStream_write(os, &len, sizeof(len));
        }
        else
        {
            int32_t len = UCMP32_kIndexCount;
            T_FileStream_write(os, &len, sizeof(len));
            T_FileStream_write(os, this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
        }
        c = (char)(this_obj->fCompact ? 1 : 0);  /* char instead of int8_t for Mac compilation*/
        T_FileStream_write(os, (const char*)&c, sizeof(c));
    }
}

U_CAPI void ucmp32_streamMemIn(CompactIntArray* this_obj, UMemoryStream* is)
{
int32_t  newCount, len;
char c;
    if (!uprv_mstrm_error(is))
    {
        
        uprv_mstrm_read(is, &newCount, sizeof(newCount));
        if (this_obj->fCount != newCount)
        {
            this_obj->fCount = newCount;
            uprv_free(this_obj->fArray);
            this_obj->fArray = 0;
            this_obj->fArray = (int32_t*)uprv_malloc(this_obj->fCount * sizeof(int32_t));
            if (!this_obj->fArray) {
                this_obj->fBogus = TRUE;
                return;
            }
        }
        uprv_mstrm_read(is, this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
        uprv_mstrm_read(is, &len, sizeof(len));
        if (len == 0)
        {
            uprv_free(this_obj->fIndex);
            this_obj->fIndex = 0;
        }
        else if (len == UCMP32_kIndexCount)
        {
            if (this_obj->fIndex == 0) 
                this_obj->fIndex =(uint16_t*)uprv_malloc(UCMP32_kIndexCount * sizeof(uint16_t));
            if (!this_obj->fIndex) {
                this_obj->fBogus = TRUE;
                uprv_free(this_obj->fArray); 
                this_obj->fArray = 0;
                return;
            }
            uprv_mstrm_read(is, this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
        }
        else
        {
            this_obj->fBogus = TRUE;
            return;
        }
        /* char instead of int8_t for Mac compilation*/
        uprv_mstrm_read(is, (char*)&c, sizeof(c));
        this_obj->fCompact = (UBool)(c != 0);
    }
}

U_CAPI void ucmp32_streamMemOut(CompactIntArray* this_obj, UMemoryStream* os)
{
    char c;
if (!uprv_mstrm_error(os))
    {
        if (this_obj->fCount != 0 && this_obj->fArray != 0)
        {
            uprv_mstrm_write(os, (uint8_t *)&(this_obj->fCount), sizeof(this_obj->fCount));
            uprv_mstrm_write(os, (uint8_t *)this_obj->fArray, sizeof(*(this_obj->fArray)) * this_obj->fCount);
        }
        else
        {
            int32_t  zero = 0;
            uprv_mstrm_write(os, (uint8_t *)&zero, sizeof(zero));
        }

        if (this_obj->fIndex == 0)
        {
            int32_t len = 0;
            uprv_mstrm_write(os, (uint8_t *)&len, sizeof(len));
        }
        else
        {
            int32_t len = UCMP32_kIndexCount;
            uprv_mstrm_write(os, (uint8_t *)&len, sizeof(len));
            uprv_mstrm_write(os, (uint8_t *)this_obj->fIndex, sizeof(*(this_obj->fIndex)) * UCMP32_kIndexCount);
        }
        c = (char)(this_obj->fCompact ? 1 : 0);  /* char instead of int8_t for Mac compilation*/
        uprv_mstrm_write(os, (uint8_t *)&c, sizeof(c));
    }
}

CompactIntArray* ucmp32_open(int32_t defaultValue)
{
  uint16_t  i;
  int32_t *p, *p_end;
  uint16_t *q, *q_end;
  CompactIntArray* this_obj = (CompactIntArray*) uprv_malloc(sizeof(CompactIntArray));
  if (this_obj == NULL) return NULL;
  
  this_obj->fStructSize = sizeof(CompactIntArray);
  this_obj->fArray = NULL;
  this_obj->fIndex = NULL;
  this_obj->fCount = UCMP32_kUnicodeCount;
  this_obj->fCompact = FALSE; 
  this_obj->fBogus = FALSE;
  this_obj->fAlias = FALSE;
  this_obj->fIAmOwned = FALSE;
  
/*set up the index array and the data array.
 * the index array always points into particular parts of the data array
 * it is initially set up to point at regular block boundaries
 * The following example uses blocks of 4 for simplicity
 * Example: Expanded
 * INDEX# 0   1   2   3   4
 * INDEX  0   4   8   12  16 ...
 * ARRAY  abcdeababcedzyabcdea...
 *        |   |   |   |   |   |...
 * whenever you set an element in the array, it unpacks to this_obj state
 * After compression, the index will point to various places in the data array
 * wherever there is a runs of the same elements as in the original
 * Example: Compressed
 * INDEX# 0   1   2   3   4
 * INDEX  0   4   1   8   2 ...
 * ARRAY  abcdeabazyabc...
 * If you look at the example, index# 2 in the expanded version points
 * to data position number 8, which has elements "bced". In the compressed
 * version, index# 2 points to data position 1, which also has "bced"
 */
 this_obj->fArray = (int32_t*)uprv_malloc(UCMP32_kUnicodeCount * sizeof(int32_t));
      if (this_obj->fArray == NULL)    {
      this_obj->fBogus = TRUE;
      return NULL;
    }
  
    this_obj->fIndex = (uint16_t*)uprv_malloc(UCMP32_kIndexCount * sizeof(uint16_t));
    if (!this_obj->fIndex) {
        uprv_free(this_obj->fArray); 
        this_obj->fArray = NULL;
        this_obj->fBogus = TRUE;
        return NULL;
    }
    p = this_obj->fArray;
    p_end = p + UCMP32_kUnicodeCount;
    while (p < p_end) *p++ = defaultValue;

    q = this_obj->fIndex;
    q_end = q + UCMP32_kIndexCount;
    i = 0;
    while (q < q_end)
    {
        *q++ = i;
        i += (1 << UCMP32_kBlockShift);
    }
    return this_obj;
}

CompactIntArray* ucmp32_openAdopt(uint16_t *indexArray,
                                  int32_t *newValues,
                                  int32_t count)
{
  CompactIntArray* this_obj = (CompactIntArray*) uprv_malloc(sizeof(CompactIntArray));

  ucmp32_initAdopt(this_obj, indexArray, newValues, count);
  this_obj->fIAmOwned = FALSE;
  return this_obj;
}

CompactIntArray* ucmp32_openAlias(uint16_t *indexArray,
                  int32_t *newValues,
                  int32_t count)
{
  CompactIntArray* this_obj = (CompactIntArray*) uprv_malloc(sizeof(CompactIntArray));

  ucmp32_initAlias(this_obj, indexArray, newValues, count);
  this_obj->fIAmOwned = FALSE;
  return this_obj;
}

CompactIntArray* ucmp32_openFromData(      const uint8_t **source, 
                                           UErrorCode *status)
{
  CompactIntArray* this_obj = (CompactIntArray*) uprv_malloc(sizeof(CompactIntArray));

  ucmp32_initFromData(this_obj, source, status);
  this_obj->fIAmOwned = FALSE;
  return this_obj;
}
/*=======================================================*/
 
CompactIntArray* ucmp32_initAdopt(CompactIntArray* this_obj,
                                  uint16_t *indexArray,
                                  int32_t *newValues,
                                  int32_t  count)
{
  if (this_obj) {
    this_obj->fCount = count; 
    this_obj->fBogus = FALSE;
    this_obj->fStructSize = sizeof(CompactIntArray);

    this_obj->fArray = newValues;
    this_obj->fIndex = indexArray;
    this_obj->fCompact = (UBool)((count < UCMP32_kUnicodeCount) ? TRUE : FALSE);
    this_obj->fAlias = FALSE;
    this_obj->fIAmOwned = TRUE;
  }

  return this_obj;
}

CompactIntArray* ucmp32_initAlias(CompactIntArray* this_obj,
                                  uint16_t *indexArray,
                                  int32_t *newValues,
                                  int32_t  count)
{
  if (this_obj) {
    this_obj->fCount = count; 
    this_obj->fBogus = FALSE;
    this_obj->fStructSize = sizeof(CompactIntArray);

    this_obj->fArray = newValues;
    this_obj->fIndex = indexArray;
    this_obj->fCompact = (UBool)((count < UCMP32_kUnicodeCount) ? TRUE : FALSE);
    this_obj->fAlias = TRUE;
    this_obj->fIAmOwned = TRUE;
  }

  return this_obj;
}
/*=======================================================*/

void ucmp32_close(CompactIntArray* this_obj) 
{
  if(this_obj != NULL) {
    if(!this_obj->fAlias) {
        if(this_obj->fArray != NULL) {
          uprv_free(this_obj->fArray);
        }
        if(this_obj->fIndex != NULL) {
          uprv_free(this_obj->fIndex);
        }
    }
    if(!this_obj->fIAmOwned) { /* Called if 'init' was called instead of 'open'. */
        uprv_free(this_obj);
    }
  }
}

UBool ucmp32_isBogus(const CompactIntArray* this_obj)
{
    return (UBool)(this_obj == NULL || this_obj->fBogus);
}

void ucmp32_expand(CompactIntArray* this_obj) {
/* can optimize later.
 * if we have to expand, then walk through the blocks instead of using Get
 * this_obj code unpacks the array by copying the blocks to the normalized position.
 * Example: Compressed
 * INDEX# 0   1   2   3   4
 * INDEX  0   4   1   8   2 ...
 * ARRAY  abcdeabazyabc...
 *  turns into
 * Example: Expanded
 * INDEX# 0   1   2   3   4
 * INDEX  0   4   8   12  16 ...
 * ARRAY  abcdeababcedzyabcdea...
 */
    int32_t i;
    int32_t* tempArray;
    if (this_obj->fCompact) {
        tempArray = (int32_t*)uprv_malloc(UCMP32_kUnicodeCount * sizeof(int32_t));
        if (tempArray == NULL) {
            this_obj->fBogus = TRUE;
            return;
        }
        for (i = 0; i < UCMP32_kUnicodeCount; ++i) {
            tempArray[i] = ucmp32_get(this_obj, (UChar)i);  /* HSYS : How expand?*/
        }
        for (i = 0; i < UCMP32_kIndexCount; ++i) {
            this_obj->fIndex[i] = (uint16_t)(i<<UCMP32_kBlockShift);
        }
        uprv_free(this_obj->fArray); 
        this_obj->fArray = tempArray;
        this_obj->fCompact = FALSE;
    }
}

uint32_t ucmp32_getCount(const CompactIntArray* this_obj)
{
    return this_obj->fCount;
}

const int32_t* ucmp32_getArray(const CompactIntArray* this_obj)
{
    return this_obj->fArray;
}

const uint16_t* ucmp32_getIndex(const CompactIntArray* this_obj)
{
    return this_obj->fIndex;
}

void  ucmp32_set(CompactIntArray* this_obj, UChar c, int32_t value)
{
    if (this_obj->fCompact == TRUE) {
        ucmp32_expand(this_obj);
        if (this_obj->fBogus) return;
    }
    this_obj->fArray[(int32_t)c] = value;
}


void ucmp32_setRange(CompactIntArray* this_obj, UChar start, UChar end, int32_t value)
{
    int32_t i;
    if (this_obj->fCompact == TRUE) {
        ucmp32_expand(this_obj);
        if (this_obj->fBogus) return;

    }
    for (i = start; i <= end; ++i) {
        this_obj->fArray[i] = value;
    }
}
/*=======================================================
 * this_obj->fArray:    an array to be overlapped
 * start and count: specify the block to be overlapped
 * tempIndex:   the overlapped array (actually indices back into inputContents)
 * inputHash:   an index of hashes for tempIndex, where
 *      inputHash[i] = XOR of values from i-count+1 to i
 */
 
static int32_t ucmp32_findOverlappingPosition(CompactIntArray* this_obj, 
                    uint32_t  start,
                    const UChar* tempIndex,
                    int32_t  tempIndexCount,
                    uint32_t  cycle) {
/* this_obj is a utility routine for finding blocks that overlap.
 * IMPORTANT: the cycle number is very important. Small cycles take a lot
 * longer to work. In some cases, they may be able to get better compaction.
 */
    int32_t  i;
    int32_t  j;
    int32_t  currentCount;
        

    for (i = 0; i < tempIndexCount; i += cycle) {
        currentCount = UCMP32_kBlockCount;
        if (i + UCMP32_kBlockCount > tempIndexCount) {
            currentCount = tempIndexCount - i;
        } 
        for (j = 0; j < currentCount; ++j) {
            if (this_obj->fArray[start + j] != this_obj->fArray[tempIndex[i + j]]) break;
        }
        if (j == currentCount) break;
    }

    return i;
}
/*=======================================================*/
 
void ucmp32_compact(CompactIntArray* this_obj, int32_t cycle) {
/* this_obj actually does the compaction.
 * it walks throught the contents of the expanded array, finding the
 * first block in the data that matches the contents of the current index.
 * As it works, it keeps an updated pointer to the last position,
 * so that it knows how big to make the final array
 * If the matching succeeds, then the index will point into the data
 * at some earlier position.
 * If the matching fails, then last position pointer will be bumped,
 * and the index will point to that last block of data.
 */
   UChar* tempIndex;
   int32_t  tempIndexCount;
   int32_t* tempArray;
   int32_t  iBlock, iIndex;
   int32_t newCount, firstPosition;
   uint32_t block;
    if (!this_obj->fCompact) {
                
        /* fix cycle, must be 0 < cycle <= blockcount*/
        if (cycle < 0) cycle = 1;
        else if (cycle > UCMP32_kBlockCount)
            cycle = UCMP32_kBlockCount;

        /* make temp storage, larger than we need*/
        tempIndex =(UChar*)uprv_malloc(UCMP32_kUnicodeCount * sizeof(uint32_t));
        if (tempIndex == NULL) {
            this_obj->fBogus = TRUE;
            return;
        }               
        /* set up first block.*/
        tempIndexCount = UCMP32_kBlockCount;
        for (iIndex = 0; iIndex < UCMP32_kBlockCount; ++iIndex) {
            tempIndex[iIndex] = (uint16_t)iIndex;
        }; /* endfor (iIndex = 0; .....)*/
        this_obj->fIndex[0] = 0;
    
    /* for each successive block, find out its first position in the compacted array*/
        for (iBlock = 1; iBlock < UCMP32_kIndexCount; ++iBlock) {
            
            block = iBlock<<UCMP32_kBlockShift;
            if (debugSmall) if (block > debugSmallLimit) break;
            firstPosition = ucmp32_findOverlappingPosition(this_obj, block, tempIndex, tempIndexCount, cycle);
            
        /* if not contained in the current list, copy the remainder
         * invariant; cumulativeHash[iBlock] = XOR of values from iBlock-kBlockCount+1 to iBlock
         * we do this_obj by XORing out cumulativeHash[iBlock-kBlockCount]
         */
            newCount = firstPosition + UCMP32_kBlockCount;
            if (newCount > tempIndexCount) {
                for (iIndex = tempIndexCount; iIndex < newCount; ++iIndex) {
                    tempIndex[iIndex] = (uint16_t)(iIndex - firstPosition + block);
                } /* endfor (iIndex = tempIndexCount....)*/
                tempIndexCount = newCount;
            } /*endif (newCount > tempIndexCount)*/
            this_obj->fIndex[iBlock] = (uint16_t)firstPosition;
        } /* endfor (iBlock = 1.....)*/
        

    /* now allocate and copy the items into the array*/
        tempArray = (int32_t*)uprv_malloc(tempIndexCount * sizeof(uint32_t));
        if (tempArray == NULL) {
            this_obj->fBogus = TRUE;
            uprv_free(tempIndex);
            return;
        }
        for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
            tempArray[iIndex] = this_obj->fArray[tempIndex[iIndex]];
        }
        uprv_free(this_obj->fArray);
        this_obj->fArray = tempArray;
        this_obj->fCount = tempIndexCount;
    

    /* free up temp storage*/
        uprv_free(tempIndex);
        this_obj->fCompact = TRUE;

#ifdef _DEBUG
        /*the following line is useful for specific debugging purposes*/
        /*fprintf(stderr, "Compacted to %ld with cycle %d\n", fCount, cycle);*/
#endif
    } /* endif (!this_obj->fCompact)*/
}

U_CAPI  uint32_t U_EXPORT2 ucmp32_flattenMem (const CompactIntArray* array, UMemoryStream *MS)
{
  int32_t size = 0;

  uprv_mstrm_write32(MS, ICU_UCMP32_VERSION);
  size += 4;
  
  uprv_mstrm_write32(MS, array->fCount);
  size += 4;

  uprv_mstrm_writeBlock(MS, array->fIndex, sizeof(array->fIndex[0])*UCMP32_kIndexCount);
  size += sizeof(array->fIndex[0])*UCMP32_kIndexCount;
  
  uprv_mstrm_writeBlock(MS, array->fArray, sizeof(array->fArray[0])*array->fCount);
  size += sizeof(array->fArray[0])*array->fCount;
  
  while(size%4) /* end padding */
  {
      uprv_mstrm_writePadding(MS, 1); /* Pad total so far to even size */
      size += 1;
  }

  return size;
}

U_CAPI  void U_EXPORT2 ucmp32_initFromData(CompactIntArray *this_obj, const uint8_t **source, UErrorCode *status)
{
  uint32_t i;
  const uint8_t *oldSource = *source;

  if(U_FAILURE(*status))
    return;

 this_obj->fArray = NULL;
 this_obj->fIndex = NULL; 
 this_obj->fBogus = FALSE;
 this_obj->fStructSize = sizeof(CompactIntArray);
 this_obj->fCompact = TRUE;
 this_obj->fAlias = TRUE;
 this_obj->fIAmOwned = TRUE;
  
 i = * ((const uint32_t*) *source);
 (*source) += 4;

 if(i != ICU_UCMP32_VERSION)
 {
   *status = U_INVALID_FORMAT_ERROR;
   return;
 }
  
 this_obj->fCount = * ((const uint32_t*)*source);
 (*source) += 4;

 this_obj->fIndex = (uint16_t*) *source;
 (*source) += sizeof(this_obj->fIndex[0])*UCMP32_kIndexCount;

 this_obj->fArray = (int32_t*) *source;
 (*source) += sizeof(this_obj->fArray[0])*this_obj->fCount;

 /* eat up padding */
 while((*source-(oldSource))%4)
    (*source)++;
}