// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =//      V E C T O R - T R E E   I M A G E   C O M P R E S S I O N// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =//           > > > >    C++ version  1.04  -  06/25/95   < < < <// Amir Said - amir@densis.fee.unicamp.br// University of Campinas (UNICAMP)// Campinas, SP 13081, Brazil// William A. Pearlman - pearlman@ecse.rpi.edu// Rensselaer Polytechnic Institute// Troy, NY 12180, USA// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -// Copyright (c) 1995 Amir Said & William A. Pearlman// This program is Copyright (c) by Amir Said & William A. Pearlman.// It may be freely redistributed in its entirety provided that this// copyright notice is not removed. It may not be sold for profit or// incorporated in commercial programs without the written permission// of the copyright holders. This program is provided as is, without any// express or implied warranty, without even the warranty of fitness// for a particular purpose.// - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - -#include "general.h"#include "image_3c.h"#include "aritcode.h"// - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - -struct Tree_Node{  Image_Coord coord;  long state;  Tree_Node * next;};// - - Static variables  - - - - - - - - - - - - - - - - - - - - - - - -const int SHF_x[4] = { 0, 0, 1, 1 }, SHF_y[4] = { 0, 1, 0, 1 };char names[3][80], * pic_f_name = names[0], * cod_f_name = names[1],      * new_f_name = names[2];Chronometer code_time, total_time;int LSP_plane, LSP_part, LSP_idx, threshold_bits, pyramid_levels;int mean[3], transf_matrix[3][3];long byte_budget, root_code;float act_value, threshold, bit_rate, rate_mult;float bias[32], * LSP_mark[32], *** LSP_mtx, ** LSP_ptr;Tree_Node * LISP_head, * LISP_end;Image_Coord dimension, pyramid_dim, root_dim, LSP_dim;Image_3C image;Adaptive_Model group_model[5], node_model[34], desc_model[34];#ifdef ENCODER  Encoder data_file;  Image_3C max_image;#else  Decoder data_file;#endif// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =//  Function Implementations// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =int Node_Transition(int old_st, const Image_Coord & pc, int * signs){ int i;  int st_trans = 0, os = old_st, ps = old_st, mask = 1;  int msk[3], count[4];  for (int i = 0; i < 4; i++) count[i] = 0;  for (i = 0; i < 4; i++, ps >>= 2) ++count[ps&0x3];  msk[0] = msk[1] = 1;  msk[2] = 1 << count[0];  int mod = count[2] - count[0] * count[1] - 1 +    (count[0] * (count[0] * (count[0] - 18) + 107)) / 6 +    (count[1] * (11 - count[1])) / 2;#ifdef ENCODER  int b = 0;#else  int b = data_file.decode_symbol(node_model[mod]);#endif  for (*signs = i = 0; i < 4; i++, mask <<= 2, os >>= 2) {    if (old_st & mask) continue;    ps = os & 0x3;#ifdef ENCODER    if (fabs(image(pc.x + SHF_x[i], pc.y + SHF_y[i])) >= threshold) {      b |= msk[ps];#else    if (b & msk[ps]) {#endif      st_trans |= mask;  ++(*signs); }    msk[ps] <<= 1; }#ifdef ENCODER  data_file.code_symbol(b, node_model[mod]);#endif  return st_trans;}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -int Desc_Transition(int old_st, const Image_Coord & pc){ int i;  int os = old_st, ps = os, st_trans = 0, mask = 2;  int msk[3], count[4];  for (int i = 0; i < 4; i++) count[i] = 0;  for (i = 0; i < 4; i++, ps >>= 2) ++count[ps & 0x3];  msk[0] = 1;  msk[1] = msk[2] = 1 << count[0];  int mod = count[2] - count[0] * count[1] - 1 +    (count[0] * (count[0] * (count[0] - 18) + 107)) / 6 +    (count[1] * (11 - count[1])) / 2;#ifdef ENCODER  int b = 0;#else  if ((old_st & 0xAA) == 0)    if (data_file.decode_symbol(group_model[count[0]])) return 0;  int b = data_file.decode_symbol(desc_model[mod]);#endif  for (i = 0; i < 4; i++, mask <<= 2, os >>= 2) {    if (old_st & mask) continue;    ps = os & 0x3;#ifdef ENCODER    if (max_image(pc.x + SHF_x[i], pc.y + SHF_y[i]) >= threshold) {      b |= msk[ps];#else    if (b & msk[ps]) {#endif      st_trans |= mask; }    msk[ps] <<= 1; }#ifdef ENCODER  if ((old_st & 0xAA) == 0) {    data_file.code_symbol(st_trans == 0, group_model[count[0]]);    if (st_trans == 0) return 0; }  data_file.code_symbol(b, desc_model[mod]);#endif  return st_trans;}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -void Output_Signs(int nb, int sd, const Image_Coord & pc){  Image_Coord nc;#ifdef ENCODER  int m = 1, b = 0;#else  int m = 1, b = data_file.decode_bits(nb);#endif  for (int i = 0; i < 4; i++, sd >>= 2)    if (sd & 1) {    nc.x = pc.x + SHF_x[i];  nc.y = pc.y + SHF_y[i];#ifdef ENCODER      if (image[nc] < 0) b |= m;#else      image[nc] = (b & m ? -act_value : act_value);#endif      if (!LSP_idx) {        NEW_VECTOR(LSP_ptr, LSP_dim.y, float *, "LSP");        LSP_mtx[LSP_part++] = LSP_ptr;  LSP_idx = LSP_dim.y; }      float * ptr = LSP_ptr[--LSP_idx] = image.address(nc);#ifdef ENCODER      if (*ptr < 0) b |= m;      *ptr = fabs(*ptr) - threshold;#else      *ptr = (b & m ? -act_value : act_value);#endif      m <<= 1; }#ifdef ENCODER  data_file.code_bits(nb, b);#endif}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -void Node_Test(Tree_Node * act_node){  int st_trans, signs;  st_trans = Node_Transition(int(act_node->state & 0xFFL),    act_node->coord, &signs);  if (st_trans) {    act_node->state |= long(st_trans);    Output_Signs(signs, st_trans, act_node->coord); }}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -void Desc_Test(Tree_Node * act_node){  Image_Coord pc = act_node->coord;  int st_trans = Desc_Transition(int(act_node->state & 0xFFL), pc);  if (!st_trans) return;  act_node->state |= st_trans;  st_trans >>= 1;  Tree_Node * new_node;  long ns = (act_node->state & 0xFFF00L) - 0x2000L;  if (ns < 0x3000L) ns |= 0xAAL;  boolean root = ((act_node->state & 0xFF000) >= root_code);  for (int i = 0; i < 4; i++, st_trans >>= 2)    if (st_trans & 0x1) {      NEW_OBJECT(new_node, Tree_Node, "LISP entry");      if (root) {        if (i == 3) ns -= 0x1000L;        new_node->coord.x = pc.x + SHF_x[i] * root_dim.x;        new_node->coord.y = pc.y + SHF_y[i] * root_dim.y; }      else {        new_node->coord.x = (pc.x + SHF_x[i]) << 1;        new_node->coord.y = (pc.y + SHF_y[i]) << 1; }      new_node->next = NULL;  new_node->state = ns;      LISP_end->next = new_node;  LISP_end = new_node;      Node_Test(new_node); }}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -int Max_Levels(int n){  int l1, l2;  for (l1 = 0; !(n & 1); l1++) n >>= 1;  for (l2 = l1 - 2; n; l2++) n >>= 1;  return (l1 < l2 ? l1 : l2) - 1;}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -boolean Sorting_Pass(void){  int color;  Tree_Node * prev = LISP_head, * node = prev;  act_value = threshold + (bias[LSP_plane] = 0.38 * threshold);  for (; node = node->next; prev = node)    if ((node->state & 0x55L) != 0x55L) {      color = int(node->state >> 8) & 0x3;      image.set_color(color);      Node_Test(node);      if (data_file.bytes_used() >= byte_budget) return true; }  for (node = prev = LISP_head; node = node->next; prev = node) {    if ((node->state & 0xAAL) != 0xAAL) {      color = int(node->state >> 8) & 0x3;      image.set_color(color);#ifdef ENCODER      max_image.set_color(color);#endif      Desc_Test(node);      if (data_file.bytes_used() >= byte_budget) return true; }    if ((node->state & 0xFFL) == 0xFFL) {      if (LISP_end == node) LISP_end = prev;      prev->next = node->next;  delete node;  node = prev; } }  return false;}// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -boolean Refinement_Pass(void){#ifdef DECODER  float t, ht1, ht2;#endif  int b, p, m, n = LSP_plane, k = LSP_dim.y;  float * ptr, * smk, ** mtx = LSP_mtx[0];  LSP_mark[LSP_plane++] = (LSP_ptr ? LSP_ptr[LSP_idx] : 0);  for (m = p = 0; p < n; p++) {#ifdef DECODER    t = bias[p];    bias[p] = threshold * (0.5 - 0.25 / Sqr(LSP_plane - p));    ht1 = bias[p] - t;  ht2 = ht1 + threshold;