;+ ; NAME: ; ice_pack ; PURPOSE: ; Compresses an integer array using a modified Rice algorithm ; CATEGORY: ; Bits and bytes ; CALLING SEQUENCE: FUNCTION ice_pack, Orig, Pack, kmax=kmax, kshift=kshift, lenbit=lenbit, sign=sign, perm=perm ; INPUTS: ; Orig array; type: long integer ; array to be compressed ; OPTIONAL INPUTS: ; kmax scalar; type: integer; default: 8 ; cutoff for applying compression (see PROCEDURE) (kmax > 0) ; kshift scalar; type: integer; default: 0 ; minimum bits copied for each difference ; lenbit scalar; type: integer; default: 16 ; # bits encoded when full value instead of a difference ; is used (see PROCEDURE) ; sign scalar; type: integer; default: 1 ; -1: all values in Orig < zero ; +1: all values in Orig >= zero ; 0: both positive and negative values are present ; perm array[0:kmax-kshift]; type: integer ; permutation table (see PROCEDURE) ; OUTPUTS: ; ibit scalar; type: long integer ; # bits in Pack used to hold the compressed data; ; on failure ibit = 0 is returned; this happens only if ; the compressed array Pack is bigger than the input ; array Orig. ; Pack array; type: long integer ; compressed data; ; The # elements in Pack is 1+(ibit-1)/nbit. ; Bits 0..ibit-1 are filled with compressed data. ; For the last element only bits 0 .. ib-1 are ; used [ib = 1+ ((ibit-1) mod nbit)]. ; INCLUDE: @compile_opt.pro ; On error, return to caller ; CALLS: ; ibclrf, ibtestf, ibsetf ; SEE ALSO: ; ice_unpack ; PROCEDURE: ; The technique is based on the algorithm described by Michael W. Richmond and Nancy E. ; Ellman, in March 1996 paper which we have in preprint form. ; COMPRESSION ALGORITHM ; --------------------- ; The Rice algorithm stores an integer in the following bit pattern: ; 0.......0 1 x.......x ; |_______| |_______| ; ipad itop + 1 ; a string of ipad 0-bits, followed by a terminating 1 bit, followed by a string of itop + 1 ; bits encoding the integer value. ; ; The actual number encoded is either the full value from the input array, or the difference ; with the previous element in the array (!!! for the first element in the array, the 'previous ; element' is assumed to be zero). ; ; The two cases are distinguished using the kmax value: if the absolute difference is less than ; 2^(kmax - 1) then the difference is encoded; if not then the full value is encoded ; ; CASE A: Non-zero absolute difference less than 2^(kmax - 1) ; ----------------------------------------------------------- ; 2^(kmax -1) has only bit kmax - 1 set. I.e. for absolute differences less than 2^(kmax - 1) this ; bit, and all higher bits, are NOT set, i.e. only the first kmax - 1 bits 0..kmax - 2 might be set. ; ; Let itop be the highest 1-bit of the absolute difference. For a non-zero difference ; 0 <= itop <= kmax-2. Since bit itop is by definition set, the absolute difference ; is fully described by the first itop bits 0...itop-1. An additional bit is needed ; to encode the sign of the difference. So itop+1 bits are needed to store the difference: ; first ipad=itop+1 0-bits, followed by a terminator 1-bit, indicate how many bits are ; used. The terminator bit is then followed by the first itop bits of the absolute difference ; followed by a sign bit. The total number of bits used is 2*itop+3. ; ; 0..........0 1 x..........x ; |__________| |__________| ; ipad=itop+1 itop+1 ; ; CASE B: Zero difference ; ----------------------- ; No bit at all is needed to store a zero, except for a terminator bit. Not that this ; is CASE A with ipad = 0, itop = -1. ; ; CASE C: Absolute difference greater/equal 2^(kmax-1) ; ----------------------------------------------------- ; In this case the full value instead of the difference is encoded. ; For case A the maximum number of leading 0-bits is kmax-1. A string of kmax 0-bits ; is used to indicate that a full value is encoded. After the terminator bit follow ; the first lenbit bits. The total number of bits used is kmax+1+lenbit ; ; 0..........0 1 x..........x ; |__________| |__________| ; ipad=kmax lenbit ; ; MINIMUM NUMBER OF BITS ; ---------------------- ; ; The above describes the the compression algorithm for the case kshift=0. ; Setting kshift to non-zero value modifies the way differences are stored: for each ; difference the kshift lowest bits are always stored. The differences are now encoded ; as follows: ; ; Zero difference (ipad = 0) ; 1 0 ; The 1-bit is the terminating bit (i.e. no leading 0-bits), followed by a 0-bit to ; indicate the presence of a zero difference. ; ; Difference needing 1..kshift bits (1 <= ipad <= kshift) ; 1 1 s x.....x ; |_____| ; kshift ; The leading 1-bit is the terminating bit (i.e. no leading 0-bits). It is followed by ; a 1-bit to be able to distinguish it from a zero difference. Then a bit follows ; storing the sign of the difference (s-bit). Then follow the lowest kshift bits. ; ; Differences needing kshift+1...kmax-1 bits (kmax-1 <= ipad <= kmax-1 above) ; 0.......0 1 x........x ; |_______| |________| ; ipad-kshift ipad ; ; Full value (ipad=kmax) ; 0.......0 1 x........x ; |_______| |________| ; kmax-kshift lenbit ; ; ; PERMUTATION TABLE ; ----------------- ; ; The number of leading 0-bits varies from izero=0 to izero=kmax-kshift. These differences ; serve merely as identifiers for the type of information stored after the terminating ; 1-bit. Rather than using them directly as described above, it is more efficient to ; use a permutation table based on the histogram of the number of bits needed for to store ; the differences. E.g. if for some sky image 3-bit difference occur most, followed by 2-bit, ; then 1-bit, then 0-bit, then 4-bit, 5-bit, etc. then the permutation table would be ; perm = 3,2,1,0,4,5...kmax-kshift ; MODIFICATION HISTORY: ; AUG-2000, Paul Hick (UCSD; pphick@ucsd.edu) ; Rewrite of Andy Buffington's ricearc.for. ; Main modifications: ; - large intermediate byte array for storing individual bits is removed ; - # leading zeroes used to store full values was reduced from kmax+1 to kmax ; - use of kshift allows for slightly better compression ; 8/24/2000, Kevin Nguyen ; - Rewrite the code from fortran to idl ;- ; Set up default compression parameters InitVar, kmax , 8 InitVar, kshift , 0 InitVar, lenbit , 16 InitVar, sign , 1 InitVar, perm , lindgen(kmax-kshift+1) nOrig = n_elements(Orig) Pack = lonarr(nOrig) ;clear all bits in Pack bitmax = nOrig*nbit - 1L ;# last available bit in Pack nbit = 32L nbit1 = nbit - 1L rank = lindgen(32L) topbit = lenbit - 1L rank = 0L*perm rank[perm] = lindgen(kmax-kshift+1) ;FOR i=0L, kmax-kshift DO rank[perm[i]] = i delmax = ibsetf(0L, kmax - 1L) ;differences larger than delmax are not compressed ibit = -1L ;Pack is filled already up to bit ibit iprev = 0L ; the '0th' element of Orig FOR i = 0L, nOrig - 1 DO BEGIN IF ibit EQ bitmax THEN RETURN, 0 idel = Orig[i] - iprev ;Difference with previous element idelabs = abs(idel) ;Absolute difference ;Test how to encode IF idel EQ 0 THEN BEGIN ;Zero difference ;Zero difference is a special case. No zero bits and no sign bit are needed, so itop+1 = 0 itop = -1L ipad = 0L ENDIF ELSE IF idelabs LT delmax THEN BEGIN;YES: small enough difference ienc = idelabs ;Find the number of bits needed to describe the difference. There will be itop+1 bits, ;including a sign bit. Store with itop+1 zeroes, a one, then the itop+1 bits. ;Here 1 <= idelabs < delmax, i.e. at least one bit of idelabs is set, and bits [kmax-1,nbit-1] ;are zero. Only kmax-1 bits [0,kmax-2] can be non-zero. Find the highest non-zero bit, ;itop <= kmax-2. Since this bit is always set we don't need to store it. ;Only the preceding itop bits [0,itop-1] need to be stored. ;(except for an additional sign bit, see below). itop = kmax - 2L WHILE NOT ibtestf(ienc, itop) DO itop -= 1L ipad = itop + 1L ;Copy the sign bit (bit nbit-1) of the non-zero difference idel to bit itop of ienc. ;Since we know that bit itop of ienc is set (it's the highest non-zero bit), ;we only need to clear it if necessary. ;If ipad <= kshift don't move the sign (it is stored separately later). IF ipad GT kshift AND NOT ibtestf(idel, nbit1) THEN $ inenc = ibclrf(ienc, itop) ;No Rice encoding ENDIF ELSE BEGIN ;Mark Pack with kmax zeroes followed by a one, and the full word ;(i.e. NOT the difference) for a total of kmax+1+lenbit bits. ;We always encode the absolute value of Orig, and if required (i.e. if sign = 0) ;add a bit for the sign. ipad = kmax itop = topbit ienc = abs(Orig[i]) ;Pick up array value ;If sign = 0 (both positive and negative values in Orig) then we need to ;encode the sign in bit topbit. IF sign EQ 0 THEN BEGIN IF ibtestf(Orig[i], nbit1) THEN ienc = ibsetf(ienc, itop) ENDIF ENDELSE ibit += rank[(ipad - kshift) > 0] ;Skip ipad - kshift zero bits ibit += 1L ;Set bit ipad+1 to 1 iPack = ibit/nbit Pack[ipack] = ibsetf(Pack[iPack], ibit mod nbit) ;If kshift > 0 an extra bit is needed to identify zero differences from differences ;described by ipad <= kshift bits. For a non-zero differences an additional bit is ;needed to store the sign. IF kshift GT 0 AND ipad LE kshift THEN BEGIN ibit += 1L iPack = ibit/nbit IF ipad GE 1 THEN BEGIN Pack[iPack] = ibsetf(Pack[iPack], ibit mod nbit) ibit += 1L iPack = ibit/nbit IF ibtestf(idel, nbit1) THEN Pack[iPack] = ibsetf(Pack[iPack], ibit mod nbit) ENDIF ENDIF ;Now transfer most-significant itop+1 bits (bits [0,itop]) of ienc to Pack ;Remember that itop=-1 for zero differences. Move at least kshift bits unless itop=-1. ;If itop=-1 then even for kshift > 0 it is not necessay to write kshift zeroes, since the ;preceeding 0-bit already indicates this condition. IF itop NE -1 THEN BEGIN FOR k = 0L, itop > (kshift-1) DO BEGIN ibit += 1L iPack = ibit/nbit IF ibtestf(ienc, k) THEN Pack[iPack] = ibsetf(Pack[iPack], ibit mod nbit) ENDFOR ENDIF iprev = Orig[i] ENDFOR Pack = Pack[0:iPack] ; Drop unused elements of Pack RETURN, ibit + 1L & END ; Return # bits in Pack used