1ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 2ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru******************************************************************************* 3ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* 4b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho* Copyright (C) 1999-2011, International Business Machines 5ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* Corporation and others. All Rights Reserved. 6ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* 7ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru******************************************************************************* 883a171d1a62abf406f7f44ae671823d5ec20db7dCraig Cornelius* file name: ucol_wgt.cpp 9ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* encoding: US-ASCII 10ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* tab size: 8 (not used) 11ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* indentation:4 12ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* 13ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* created on: 2001mar08 14ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* created by: Markus W. Scherer 15ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* 16ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* This file contains code for allocating n collation element weights 17ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* between two exclusive limits. 18ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru* It is used only internally by ucol_bld. 19ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru*/ 20ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 21ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "unicode/utypes.h" 22ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 23ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#if !UCONFIG_NO_COLLATION 24ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 25ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "ucol_imp.h" 26ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "ucol_wgt.h" 27ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "cmemory.h" 28ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#include "uarrsort.h" 29ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 30ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 31ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru# include <stdio.h> 32ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 33ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 34ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* collation element weight allocation -------------------------------------- */ 35ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 36ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* helper functions for CE weights */ 37ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 3883a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline int32_t 39ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerulengthOfWeight(uint32_t weight) { 40ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if((weight&0xffffff)==0) { 41ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 1; 42ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else if((weight&0xffff)==0) { 43ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 2; 44ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else if((weight&0xff)==0) { 45ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 3; 46ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 47ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 4; 48ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 49ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 50ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 5183a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 52ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerugetWeightTrail(uint32_t weight, int32_t length) { 53ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (uint32_t)(weight>>(8*(4-length)))&0xff; 54ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 55ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 5683a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 57ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerusetWeightTrail(uint32_t weight, int32_t length, uint32_t trail) { 58ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru length=8*(4-length); 59ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length)); 60ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 61ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 6283a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 63db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste QuerugetWeightByte(uint32_t weight, int32_t idx) { 64db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste Queru return getWeightTrail(weight, idx); /* same calculation */ 65ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 66ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 6783a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 68db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste QuerusetWeightByte(uint32_t weight, int32_t idx, uint32_t byte) { 69ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */ 70ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 71db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste Queru idx*=8; 72b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho if(idx<32) { 73b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho mask=((uint32_t)0xffffffff)>>idx; 74b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } else { 75b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // Do not use uint32_t>>32 because on some platforms that does not shift at all 76b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // while we need it to become 0. 77b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // PowerPC: 0xffffffff>>32 = 0 (wanted) 78b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // x86: 0xffffffff>>32 = 0xffffffff (not wanted) 79b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // 80b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // ANSI C99 6.5.7 Bitwise shift operators: 81b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // "If the value of the right operand is negative 82b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // or is greater than or equal to the width of the promoted left operand, 83b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho // the behavior is undefined." 84b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho mask=0; 85b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho } 86db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste Queru idx=32-idx; 87db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste Queru mask|=0xffffff00<<idx; 88db20b09c124abfd4c87566c93fe35276b1382b61Jean-Baptiste Queru return (uint32_t)((weight&mask)|(byte<<idx)); 89ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 90ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 9183a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 92ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerutruncateWeight(uint32_t weight, int32_t length) { 93ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (uint32_t)(weight&(0xffffffff<<(8*(4-length)))); 94ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 95ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 9683a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 97ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruincWeightTrail(uint32_t weight, int32_t length) { 98ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (uint32_t)(weight+(1UL<<(8*(4-length)))); 99ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 100ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 10183a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 102ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerudecWeightTrail(uint32_t weight, int32_t length) { 103ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return (uint32_t)(weight-(1UL<<(8*(4-length)))); 104ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 105ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 10683a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline uint32_t 107ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruincWeight(uint32_t weight, int32_t length, uint32_t maxByte) { 108ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t byte; 109ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 110ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(;;) { 111ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru byte=getWeightByte(weight, length); 112ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(byte<maxByte) { 113ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return setWeightByte(weight, length, byte+1); 114ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 115ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* roll over, set this byte to UCOL_BYTE_FIRST_TAILORED and increment the previous one */ 116ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=setWeightByte(weight, length, UCOL_BYTE_FIRST_TAILORED); 117ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru --length; 118ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 119ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 120ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 121ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 12283a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline int32_t 123ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerulengthenRange(WeightRange *range, uint32_t maxByte, uint32_t countBytes) { 124ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t length; 125ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 126ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru length=range->length2+1; 127ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru range->start=setWeightTrail(range->start, length, UCOL_BYTE_FIRST_TAILORED); 128ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru range->end=setWeightTrail(range->end, length, maxByte); 129ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru range->count2*=countBytes; 130ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru range->length2=length; 131ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return length; 132ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 133ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 134ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* for uprv_sortArray: sort ranges in weight order */ 135ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Querustatic int32_t U_CALLCONV 13627f654740f2a26ad62a5c155af9199af9e69b889clairehocompareRanges(const void * /*context*/, const void *left, const void *right) { 137ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t l, r; 138ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 139ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru l=((const WeightRange *)left)->start; 140ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru r=((const WeightRange *)right)->start; 141ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(l<r) { 142ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return -1; 143ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else if(l>r) { 144ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 1; 145ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 146ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 147ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 148ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 149ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 150ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 151ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * take two CE weights and calculate the 152ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * possible ranges of weights between the two limits, excluding them 153ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * for weights with up to 4 bytes there are up to 2*4-1=7 ranges 154ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 15583a171d1a62abf406f7f44ae671823d5ec20db7dCraig Corneliusstatic inline int32_t 156ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerugetWeightRanges(uint32_t lowerLimit, uint32_t upperLimit, 157ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t maxByte, uint32_t countBytes, 158ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru WeightRange ranges[7]) { 159ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */ 160ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t weight, trail; 161ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t length, lowerLength, upperLength, rangeCount; 162ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 163ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* assume that both lowerLimit & upperLimit are not 0 */ 164ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 165ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* get the lengths of the limits */ 166ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lowerLength=lengthOfWeight(lowerLimit); 167ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upperLength=lengthOfWeight(upperLimit); 168ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 169ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 170ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength); 171ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength); 172ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 173ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 174ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lowerLimit>=upperLimit) { 175ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 176ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("error: no space between lower & upper limits\n"); 177ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 178ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 179ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 180ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 181ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* check that neither is a prefix of the other */ 182ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lowerLength<upperLength) { 183ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lowerLimit==truncateWeight(upperLimit, lowerLength)) { 184ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 185ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit); 186ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 187ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 188ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 189ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 190ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */ 191ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 192ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* reset local variables */ 193ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memset(lower, 0, sizeof(lower)); 194ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memset(&middle, 0, sizeof(middle)); 195ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memset(upper, 0, sizeof(upper)); 196ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 197ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* 198ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * With the limit lengths of 1..4, there are up to 7 ranges for allocation: 199ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * range minimum length 200ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * lower[4] 4 201ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * lower[3] 3 202ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * lower[2] 2 203ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * middle 1 204ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * upper[2] 2 205ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * upper[3] 3 206ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * upper[4] 4 207ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * 208ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * We are now going to calculate up to 7 ranges. 209ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * Some of them will typically overlap, so we will then have to merge and eliminate ranges. 210ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 211ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=lowerLimit; 212ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=lowerLength; length>=2; --length) { 213ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru trail=getWeightTrail(weight, length); 214ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(trail<maxByte) { 215ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].start=incWeightTrail(weight, length); 216ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].end=setWeightTrail(weight, length, maxByte); 217ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].length=length; 218ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].count=maxByte-trail; 219ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 220ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=truncateWeight(weight, length-1); 221ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 222ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru middle.start=incWeightTrail(weight, 1); 223ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 224ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=upperLimit; 225ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=upperLength; length>=2; --length) { 226ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru trail=getWeightTrail(weight, length); 227ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(trail>UCOL_BYTE_FIRST_TAILORED) { 228ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upper[length].start=setWeightTrail(weight, length, UCOL_BYTE_FIRST_TAILORED); 229ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upper[length].end=decWeightTrail(weight, length); 230ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upper[length].length=length; 231ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upper[length].count=trail-UCOL_BYTE_FIRST_TAILORED; 232ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 233ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=truncateWeight(weight, length-1); 234ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 235ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru middle.end=decWeightTrail(weight, 1); 236ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 237ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the middle range */ 238ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru middle.length=1; 239ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(middle.end>=middle.start) { 240ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru middle.count=(int32_t)((middle.end-middle.start)>>24)+1; 241ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 242ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* eliminate overlaps */ 243ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t start, end; 244ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 245ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* remove the middle range */ 246ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru middle.count=0; 247ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 248ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* reduce or remove the lower ranges that go beyond upperLimit */ 249ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=4; length>=2; --length) { 250ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lower[length].count>0 && upper[length].count>0) { 251ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru start=upper[length].start; 252ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru end=lower[length].end; 253ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 254ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(end>=start || incWeight(end, length, maxByte)==start) { 255ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */ 256ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru start=lower[length].start; 257ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru end=lower[length].end=upper[length].end; 258ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* 259ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * merging directly adjacent ranges needs to subtract the 0/1 gaps in between; 260ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * it may result in a range with count>countBytes 261ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 262ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].count= 263ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru (int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+ 264ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru countBytes*(getWeightByte(end, length-1)-getWeightByte(start, length-1))); 265ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru upper[length].count=0; 266ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while(--length>=2) { 267ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lower[length].count=upper[length].count=0; 268ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 269ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru break; 270ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 271ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 272ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 273ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 274ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 275ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 276ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* print ranges */ 277ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=4; length>=2; --length) { 278ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lower[length].count>0) { 279ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count); 280ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 281ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 282ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(middle.count>0) { 283ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count); 284ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 285ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=2; length<=4; ++length) { 286ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(upper[length].count>0) { 287ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count); 288ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 289ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 290ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 291ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 292ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* copy the ranges, shortest first, into the result array */ 293ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=0; 294ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(middle.count>0) { 295ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memcpy(ranges, &middle, sizeof(WeightRange)); 296ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=1; 297ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 298ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(length=2; length<=4; ++length) { 299ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* copy upper first so that later the middle range is more likely the first one to use */ 300ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(upper[length].count>0) { 301ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange)); 302ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ++rangeCount; 303ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 304ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(lower[length].count>0) { 305ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange)); 306ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ++rangeCount; 307ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 308ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 309ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return rangeCount; 310ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 311ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 312ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 313ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * call getWeightRanges and then determine heuristically 314ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * which ranges to use for a given number of weights between (excluding) 315ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * two limits 316ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 317ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_CFUNC int32_t 318ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruucol_allocWeights(uint32_t lowerLimit, uint32_t upperLimit, 319ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t n, 320ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t maxByte, 321ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru WeightRange ranges[7]) { 322ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* number of usable byte values 3..maxByte */ 323ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t countBytes=maxByte-UCOL_BYTE_FIRST_TAILORED+1; 324ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 325ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t lengthCounts[6]; /* [0] unused, [5] to make index checks unnecessary */ 326ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t maxCount; 327ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t i, rangeCount, minLength/*, maxLength*/; 328ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 329ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* countBytes to the power of index */ 330ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t powers[5]; 331ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* gcc requires explicit initialization */ 332ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru powers[0] = 1; 333ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru powers[1] = countBytes; 334ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru powers[2] = countBytes*countBytes; 335ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru powers[3] = countBytes*countBytes*countBytes; 336ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru powers[4] = countBytes*countBytes*countBytes*countBytes; 337ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 338ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 339ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru puts(""); 340ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 341ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 342ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=getWeightRanges(lowerLimit, upperLimit, maxByte, countBytes, ranges); 343ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(rangeCount<=0) { 344ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 345ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("error: unable to get Weight ranges\n"); 346ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 347ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 348ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 349ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 350ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* what is the maximum number of weights with these ranges? */ 351ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru maxCount=0; 352ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(i=0; i<rangeCount; ++i) { 353ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru maxCount+=(uint32_t)ranges[i].count*powers[4-ranges[i].length]; 354ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 355ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(maxCount>=n) { 356ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 357ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("the maximum number of %lu weights is sufficient for n=%lu\n", maxCount, n); 358ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 359ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 360ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 361ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("error: the maximum number of %lu weights is insufficient for n=%lu\n", maxCount, n); 362ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 363ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 364ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 365ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 366ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the length2 and count2 fields */ 367ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(i=0; i<rangeCount; ++i) { 368ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[i].length2=ranges[i].length; 369ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[i].count2=(uint32_t)ranges[i].count; 370ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 371ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 372ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* try until we find suitably large ranges */ 373ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(;;) { 374ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* get the smallest number of bytes in a range */ 375ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru minLength=ranges[0].length2; 376ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 377ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* sum up the number of elements that fit into ranges of each byte length */ 378ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memset(lengthCounts, 0, sizeof(lengthCounts)); 379ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(i=0; i<rangeCount; ++i) { 380ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lengthCounts[ranges[i].length2]+=ranges[i].count2; 381ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 382ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 383ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* now try to allocate n elements in the available short ranges */ 384ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(n<=(lengthCounts[minLength]+lengthCounts[minLength+1])) { 385ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* trivial cases, use the first few ranges */ 386ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru maxCount=0; 387ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=0; 388ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru do { 389ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru maxCount+=ranges[rangeCount].count2; 390ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ++rangeCount; 391ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } while(n>maxCount); 392ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 393ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("take first %ld ranges\n", rangeCount); 394ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 395ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru break; 396ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else if(n<=ranges[0].count2*countBytes) { 397ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* easy case, just make this one range large enough by lengthening it once more, possibly split it */ 398ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t count1, count2, power_1, power; 399ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 400ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /*maxLength=minLength+1;*/ 401ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 402ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* calculate how to split the range between maxLength-1 (count1) and maxLength (count2) */ 403ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru power_1=powers[minLength-ranges[0].length]; 404ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru power=power_1*countBytes; 405ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru count2=(n+power-1)/power; 406ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru count1=ranges[0].count-count2; 407ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 408ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* split the range */ 409ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 410ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("split the first range %ld:%ld\n", count1, count2); 411ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 412ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(count1<1) { 413ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=1; 414ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 415ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* lengthen the entire range to maxLength */ 416ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lengthenRange(ranges, maxByte, countBytes); 417ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 418ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* really split the range */ 419ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t byte; 420ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 421ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* create a new range with the end and initial and current length of the old one */ 422ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=2; 423ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].end=ranges[0].end; 424ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].length=ranges[0].length; 425ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].length2=minLength; 426ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 427ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the end of the first range according to count1 */ 428ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru i=ranges[0].length; 429ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru byte=getWeightByte(ranges[0].start, i)+count1-1; 430ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 431ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* 432ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * ranges[0].count and count1 may be >countBytes 433ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * from merging adjacent ranges; 434ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * byte>maxByte is possible 435ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 436ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(byte<=maxByte) { 437ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].end=setWeightByte(ranges[0].start, i, byte); 438ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else /* byte>maxByte */ { 439ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].end=setWeightByte(incWeight(ranges[0].start, i-1, maxByte), i, byte-countBytes); 440ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 441ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 442ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the bytes in the end weight at length+1..length2 to maxByte */ 443ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru byte=(maxByte<<24)|(maxByte<<16)|(maxByte<<8)|maxByte; /* this used to be 0xffffffff */ 444ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].end=truncateWeight(ranges[0].end, i)| 445ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ((byte>>(8*i))&(byte<<(8*(4-minLength)))); 446ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 447ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the start of the second range to immediately follow the end of the first one */ 448ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].start=incWeight(ranges[0].end, minLength, maxByte); 449ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 450ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set the count values (informational) */ 451ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].count=count1; 452ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].count=count2; 453ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 454ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].count2=count1*power_1; 455ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[1].count2=count2*power_1; /* will be *countBytes when lengthened */ 456ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 457ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* lengthen the second range to maxLength */ 458ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lengthenRange(ranges+1, maxByte, countBytes); 459ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 460ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru break; 461ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 462ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 463ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* no good match, lengthen all minLength ranges and iterate */ 464ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 465ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1); 466ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 467ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(i=0; ranges[i].length2==minLength; ++i) { 468ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru lengthenRange(ranges+i, maxByte, countBytes); 469ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 470ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 471ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 472ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(rangeCount>1) { 473ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* sort the ranges by weight values */ 474ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru UErrorCode errorCode=U_ZERO_ERROR; 475ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_sortArray(ranges, rangeCount, sizeof(WeightRange), compareRanges, NULL, FALSE, &errorCode); 476ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* ignore error code: we know that the internal sort function will not fail here */ 477ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 478ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 479ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#ifdef UCOL_DEBUG 480ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru puts("final ranges:"); 481ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru for(i=0; i<rangeCount; ++i) { 482ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .length2=%ld .count=%ld .count2=%lu\n", 483ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].length2, ranges[i].count, ranges[i].count2); 484ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 485ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 486ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 487ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* set maxByte in ranges[0] for ucol_nextWeight() */ 488ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].count=maxByte; 489ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 490ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return rangeCount; 491ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 492ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 493ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru/* 494ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * given a set of ranges calculated by ucol_allocWeights(), 495ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru * iterate through the weights 496ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru */ 497ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QueruU_CFUNC uint32_t 498ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruucol_nextWeight(WeightRange ranges[], int32_t *pRangeCount) { 499ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(*pRangeCount<=0) { 500ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0xffffffff; 501ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 502ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t weight, maxByte; 503ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 504ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* get maxByte from the .count field */ 505ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru maxByte=ranges[0].count; 506ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 507ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* get the next weight */ 508ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=ranges[0].start; 509ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(weight==ranges[0].end) { 510ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* this range is finished, remove it and move the following ones up */ 511ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(--*pRangeCount>0) { 512ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uprv_memmove(ranges, ranges+1, *pRangeCount*sizeof(WeightRange)); 513ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].count=maxByte; /* keep maxByte in ranges[0] */ 514ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 515ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } else { 516ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru /* increment the weight for the next value */ 517ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru ranges[0].start=incWeight(weight, ranges[0].length2, maxByte); 518ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 519ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 520ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return weight; 521ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 522ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 523ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 52427f654740f2a26ad62a5c155af9199af9e69b889claireho#if 0 // #ifdef UCOL_DEBUG 525ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 526ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Querustatic void 527ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste QuerutestAlloc(uint32_t lowerLimit, uint32_t upperLimit, uint32_t n, UBool enumerate) { 528ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru WeightRange ranges[8]; 529ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru int32_t rangeCount; 530ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 531ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru rangeCount=ucol_allocWeights(lowerLimit, upperLimit, n, ranges); 532ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(enumerate) { 533ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru uint32_t weight; 534ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 535ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru while(n>0) { 536ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru weight=ucol_nextWeight(ranges, &rangeCount); 537ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru if(weight==0xffffffff) { 538ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf("error: 0xffffffff with %lu more weights to go\n", n); 539ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru break; 540ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 541ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru printf(" 0x%08lx\n", weight); 542ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru --n; 543ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 544ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru } 545ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 546ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 547ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queruextern int 548ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Querumain(int argc, const char *argv[]) { 549ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#if 0 550ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 551ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x364214fc, 0x44b87d23, 5, FALSE); 552ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x44b87d23, 5, FALSE); 553ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x44b87d23, 20, FALSE); 554ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x44b87d23, 13700, FALSE); 555ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x38b87d23, 1, FALSE); 556ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x38b87d23, 20, FALSE); 557ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x38b87d23, 200, TRUE); 558ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x38b87d23, 13700, FALSE); 559ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x37b87d23, 13700, FALSE); 560ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36ef1500, 0x37b87d23, 13700, FALSE); 561ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36421500, 0x36b87d23, 13700, FALSE); 562ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x36b87122, 0x36b87d23, 13700, FALSE); 563ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x49000000, 0x4a600000, 13700, FALSE); 564ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x9fffffff, 0xd0000000, 13700, FALSE); 565ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x9fffffff, 0xd0000000, 67400, FALSE); 566ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x9fffffff, 0xa0030000, 67400, FALSE); 567ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0x9fffffff, 0xa0030000, 40000, FALSE); 568ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0xa0000000, 0xa0030000, 40000, FALSE); 569ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru testAlloc(0xa0031100, 0xa0030000, 40000, FALSE); 570ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#if 0 571ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 572ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru return 0; 573ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru} 574ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 575ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif 576ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru 577ac04d0bbe12b3ef54518635711412f178cb4d16Jean-Baptiste Queru#endif /* #if !UCONFIG_NO_COLLATION */ 578