<?php
// $Id$

/**
 *  This contains functions defined to help with decoding huffman encodings
 */

// read a series of bits from a byte array
function _mapi_video_get_bits(&$array, &$index, &$bit, $count) {
  // reads the appropriate bits
  $pos = 0;
  $value = 0;
  while ($count > 0) {
    // switch to next byte
    if ($bit > 7) {
      $index += 1;
      $bit = 0;
    }
    $value |= (($array[$index] >> $bit) & 1) << $pos;
    $bit += 1;
    $pos += 1;
    $count -= 1;
  }

  return $value;
}


// constructs a huffman tree table from a table of frequencys
function _mapi_video_huffman_construct($table, $max) {
  $numcodes = count($table);
  $count = array_pad(array(), $max + 1, 0);

  // get count of symbols
  for ($symbol = 0; $symbol < $numcodes; $symbol++) {
    $count[$table[$symbol]]++;
  }
  if ($count[0] == $numcodes) {
    return array();
  }

  // generate offsets into symbol table for each length for sorting
  $offsets = array(1 => 0);
  for ($len = 1; $len < $max; $len++) {
    $offsets[$len + 1] = $offsets[$len] + $count[$len];
  }

  $symbols = array();
  for ($symbol = 0; $symbol < $numcodes; $symbol++) {
    if ($table[$symbol] != 0) {
      $symbols[$offsets[$table[$symbol]]++] = $symbol;
    }
  }

  return array('count' => $count, 'symbols' => $symbols);
}

// reads the next code from the array using a huffman table
function _mapi_video_huffman_decode($table, &$block, &$index, &$bit, $max) {
  $code = $first = $i = 0;
  for ($len = 1; $len <= $max; $len++) {
    $code |= _mapi_video_get_bits($block, $index, $bit, 1);
    $count = $table['count'][$len];
    if ($code < $first + $count) {
      return $table['symbols'][$i + ($code - $first)];
    }
    $i += $count;
    $first += $count;
    $first <<= 1;
    $code <<= 1;
  }
  return FALSE;
}
