lib/Bzip2.js
function(freq, alphabetSize) {
  // As in BZip2HuffmanStageEncoder.java (from jbzip2):
  // The Huffman allocator needs its input symbol frequencies to be
  // sorted, but we need to return code lengths in the same order as
  // the corresponding frequencies are passed in.
  // The symbol frequency and index are merged into a single array of
  // integers - frequency in the high 23 bits, index in the low 9
  // bits.
  //     2^23 = 8,388,608 which is higher than the maximum possible
  //            frequency for one symbol in a block
  //     2^9 = 512 which is higher than the maximum possible
  //            alphabet size (== 258)
  // Sorting this array simultaneously sorts the frequencies and
  // leaves a lookup that can be used to cheaply invert the sort
  var i, mergedFreq = [];
  for (i=0; i<alphabetSize; i++) {
    mergedFreq[i] = (freq[i] << 9) | i;
  }
  mergedFreq.sort(function(a,b) { return a-b; });
  var sortedFreq = mergedFreq.map(function(v) { return v>>>9; });
  // allocate code lengths in place. (result in sortedFreq array)
  HuffmanAllocator.allocateHuffmanCodeLengths(sortedFreq, MAX_HUFCODE_BITS);
  // reverse the sort to put codes & code lengths in order of input symbols
  this.codeLengths = Util.makeU8Buffer(alphabetSize);
  for (i=0; i<alphabetSize; i++) {
    var sym = mergedFreq[i] & 0x1FF;
    this.codeLengths[sym] = sortedFreq[i];
  }
}
function(freq, alphabetSize) {
  // As in BZip2HuffmanStageEncoder.java (from jbzip2):
  // The Huffman allocator needs its input symbol frequencies to be
  // sorted, but we need to return code lengths in the same order as
  // the corresponding frequencies are passed in.
  // The symbol frequency and index are merged into a single array of
  // integers - frequency in the high 23 bits, index in the low 9
  // bits.
  //     2^23 = 8,388,608 which is higher than the maximum possible
  //            frequency for one symbol in a block
  //     2^9 = 512 which is higher than the maximum possible
  //            alphabet size (== 258)
  // Sorting this array simultaneously sorts the frequencies and
  // leaves a lookup that can be used to cheaply invert the sort
  var i, mergedFreq = [];
  for (i=0; i<alphabetSize; i++) {
    mergedFreq[i] = (freq[i] << 9) | i;
  }
  mergedFreq.sort(function(a,b) { return a-b; });
  var sortedFreq = mergedFreq.map(function(v) { return v>>>9; });
  // allocate code lengths in place. (result in sortedFreq array)
  HuffmanAllocator.allocateHuffmanCodeLengths(sortedFreq, MAX_HUFCODE_BITS);
  // reverse the sort to put codes & code lengths in order of input symbols
  this.codeLengths = Util.makeU8Buffer(alphabetSize);
  for (i=0; i<alphabetSize; i++) {
    var sym = mergedFreq[i] & 0x1FF;
    this.codeLengths[sym] = sortedFreq[i];
  }
}
function ( freq , alphabetSize ) { // As in BZip2HuffmanStageEncoder.java (from jbzip2): // The Huffman allocator needs its input symbol frequencies to be // sorted, but we need to return code lengths in the same order as // the corresponding frequencies are passed in. // The symbol frequency and index are merged into a single array of // integers - frequency in the high 23 bits, index in the low 9 // bits. //     2^23 = 8,388,608 which is higher than the maximum possible //            frequency for one symbol in a block //     2^9 = 512 which is higher than the maximum possible //            alphabet size (== 258) // Sorting this array simultaneously sorts the frequencies and // leaves a lookup that can be used to cheaply invert the sort var i , mergedFreq = [ ] ; for ( i = 0 ; i < alphabetSize ; i ++ ) { mergedFreq [ i ] = ( freq [ i ] << 9 ) | i ; } mergedFreq . sort ( function ( a , b ) { return a - b ; } ) ; var sortedFreq = mergedFreq . map ( function ( v ) { return v >>> 9 ; } ) ; // allocate code lengths in place. (result in sortedFreq array) HuffmanAllocator . allocateHuffmanCodeLengths ( sortedFreq , MAX_HUFCODE_BITS ) ; // reverse the sort to put codes & code lengths in order of input symbols this . codeLengths = Util . makeU8Buffer ( alphabetSize ) ; for ( i = 0 ; i < alphabetSize ; i ++ ) { var sym = mergedFreq [ i ] & 0x1FF ; this . codeLengths [ sym ] = sortedFreq [ i ] ; } }
create a Huffman tree from the table of frequencies
create a Huffman tree from the table of frequencies