ocrm.c

在linux系统下开发研究移动通信的工具型代码

/*
 * $Log: ocrm.c,v $
 * Revision 1.1  2000/05/03 14:30:04  bjc97r
 * Initial revision
 *
 */
char *_ocrm_id = "$Id: ocrm.c,v 1.1 2000/05/03 14:30:04 bjc97r Exp $";

#include <stdio.h>
#include <stdlib.h>

/* The maximum allowed code length : 2^12 = 4096 */
#define MAX_DEGREE 12

/* The maximum number of tree structured multi-rate orthogonal code set */
#define MAX_CODE_TREE 10

/* Orthogonal Code Resource Allocation Status
   FREE: available for use,
   USED: being used,
   FORBIDDEN: forbidden by orthogonality preservation algorithm
              as a dependent orthogonal code is being used */
typedef enum { FREE, USED, FORBIDDEN } OCodeState;

/* Code Generation Algorithm
   OH: original Hadamard transform or Sylvester construction,
   MH: modified Hadamard transform as in Adachi's paper */
typedef enum { OH, MH } OCodeGenMode;

typedef struct {
  int        index; /* The orthogonal code index */
  OCodeState state; /* the period of the base orthogonal Gold code */
} OCodeNode;

typedef struct {
  int       base_deg; /* the base orthogonal code degree */
  int       max_deg;  /* the maximum expanded orthogonal degree */
  OCodeNode *nodes;   /* the node array */
  char      used;     /* 1 when this tree is valid */
} OCodeTree;

static OCodeTree *ocrm_table;
static char is_initialized = 0;

int ocrm_init( void )
  /* It initializes the  OCodeTree table entries.
     ocrm_init() should be called before any ocrm- functions.
     0 is returned on successful initialization. */
{
  if ( !is_initialized ) {
    int i;
    
    ocrm_table = (OCodeTree*) malloc( sizeof(OCodeTree)*MAX_CODE_TREE );
    if ( ocrm_table == (OCodeTree*)NULL ) {
      fprintf(stderr, "ocrm_init: ...cannot allocate memory!\n");
      return -1;
    }

    for ( i = 0; i < MAX_CODE_TREE; i++ ) {
      ocrm_table[i].used = 0;
    }
    is_initialized = 1;
  }

  return 0;
}

void ocrm_end( void )
  /* It deallocates ocrm_table and reset init flag */
{
  if ( is_initialized ) {
    int i;

    for( i = 0; i < MAX_CODE_TREE; i++ ) {
      if ( ocrm_table[i].used ) {
	free( ocrm_table[i].nodes );
      }
    }
    free( ocrm_table );
    is_initialized = 0;
  }
}

void hadamard_assign( int id, int deg, int pos, unsigned long index ) 
  /* It assigns the index to the specified tree node using
     the Hadamard transform method.
     The function works recursively. */
{
  if ( deg < ocrm_table[id].max_deg ) {
    hadamard_assign( id, deg+1, pos*2, index );
    hadamard_assign( id, deg+1, pos*2 + 1, index + (1 << deg) );
    if ( deg >= ocrm_table[id].base_deg ) {
      ocrm_table[id].nodes[ (1 << deg) + pos ].index = index;
    }
  }
  else {
    ocrm_table[id].nodes[ (1 << deg) + pos ].index = index;
  }
}

void modified_assign( int id )
  /* It assigns the index to the specified tree according to
     modified Hadamard transform method decribed in Adachi's paper */
{
  int deg;
  OCodeNode *the_nodes; /* the nodes pointer */

  deg = ocrm_table[id].base_deg;
  the_nodes = ocrm_table[id].nodes;

  for(; deg <= ocrm_table[id].max_deg; deg++ ) {
    int nodes_size; /* the number of code size with the degree */
    int pos;

    nodes_size = 1 << deg;
    for( pos = 0; pos < nodes_size; pos++ ) {
      the_nodes[nodes_size+pos].index = pos + 1;
    }
  }
}

void initialize_state( int id )
  /* It marks all tree nodes as FREE. */
{
  OCodeNode *the_nodes;  /* the nodes pointer */
  int        last_node;
  int        i; 

  the_nodes = ocrm_table[id].nodes;
  i         = 1 << ocrm_table[id].base_deg;
  last_node = (1 << (ocrm_table[id].max_deg + 1) ) - 1;

  for(; i <= last_node; i++ ) {
    the_nodes[i].state = FREE;
  }
}

int ocrm_create_code_tree( int base_deg, int max_deg,
			   OCodeGenMode gen_mode )
  /* It create an Multi-Rate Orthogonal code resource binary tree
     and initializes the binary tree with free orthogonal indicies
     according to the given code index generation mode.
     The code tree id is returned */
{
  unsigned id;    /* base ogold ID */

  /* Check Argument */
  if ( base_deg < 0 ) {
    fprintf(stderr, "ocrm_create: ..invalid base degree, %d!\n", base_deg );
    return -1;
  }
  if ( max_deg > MAX_DEGREE ) {
    fprintf(stderr, "ocrm_create: ..too big degree, %d!\n", base_deg );
    return -1; 
  }

  /* Get Free ID */
  for ( id = 0; ocrm_table[id].used && (id < MAX_CODE_TREE); id ++ );
  if ( id == MAX_CODE_TREE ) return -1; /* Max Code trees have been used */

  /* Allocate Tree Nodes Space */
  {
    unsigned long array_size;
    array_size = ( 1 << (max_deg+1) ) - ( 1 << base_deg );
    ocrm_table[id].nodes = (OCodeNode*) malloc( sizeof(OCodeNode)*array_size );
    if ( ocrm_table[id].nodes == (OCodeNode*) NULL ) {
      fprintf(stderr, "ocrm_create: ...cannot allocate memory!\n");
      return -1;
    }
    ocrm_table[id].nodes -= 1 << base_deg; /* adjust tree node array index */
  }

  /* Initialize Tree Nodes */
  ocrm_table[id].used     = 1;
  ocrm_table[id].base_deg = base_deg;
  ocrm_table[id].max_deg  = max_deg;
  initialize_state( id ); /* Mark all nodes as FREE */
  switch ( gen_mode ) { /* Assign orthogonal code indicies */
  case OH:
    hadamard_assign( id, 0, 0, 0 ); 
    break;
  case MH:
    modified_assign( id );
    break;
  default:
    fprintf(stderr, "ocrm_create: ..invalid code index generation mode!\n" );
    return -1;
  }

  return id;
}

void ocrm_destroy_code_tree( int id )
  /* The function deallocates the memory space for tree nodes.
     The corresponding flags are set */
{
  free( (void*) ocrm_table[id].nodes );
  ocrm_table[id].used = 0;
}

void set_subtree_state( int id, int deg, int pos, OCodeState state )
  /* Mark all the subtree as the given state */
{
  if ( deg < ocrm_table[id].max_deg ) {
    set_subtree_state( id, deg+1, pos*2, state );
    set_subtree_state( id, deg+1, pos*2 + 1, state );
    if ( deg >= ocrm_table[id].base_deg ) {
      ocrm_table[id].nodes[ (1 << deg) + pos ].state = state;
    }
  }
  else {
    ocrm_table[id].nodes[ (1 << deg) + pos ].state = state;
  }
}

int ocrm_get_code( int id, int deg, int *serial )
  /* It gives the next available orthogonal code index of 
     the given degree. The found valid code index is returned.
     The position in the code tree is saved in *serial.
     This value should be used for free the code index.
     The code index is returned if one is available,
     otherwise -1 is returned */
{
  OCodeNode *the_node;
  int i, the_index; 
  int index_limit, index_min;

  the_node = ocrm_table[id].nodes;
  index_limit = 1 << (deg+1);
  index_min   = 1 << ocrm_table[id].base_deg;

  for(i = (1<<deg); i < index_limit; i++) {
    if ( the_node[i].state == FREE ) { /* a free code is available */
      the_index = the_node[i].index;
      the_node[i].state = USED;
      *serial = i;
      /* Disable the assignment of all direct decendents */
      if ( deg < ocrm_table[id].max_deg ) {
	set_subtree_state( id, deg + 1, (i-(1<<deg))<<1, FORBIDDEN );
	set_subtree_state( id, deg + 1, ((i-(1<<deg))<<1)+1, FORBIDDEN );
      }
      /* Disable the assignment of all direct ancestors */
      for( i >>= 1; (i >= index_min) && (the_node[i].state==FREE); i >>= 1 ) {
	the_node[i].state = FORBIDDEN;
      }
      return the_index;
    }
  }

  /* no free code is available */
  return -1;
}

void ocrm_free_code( int id, int serial )
  /* It makes the code index available. */
{
  OCodeNode *the_node;
  int index_upper_limit, index_lower_limit;
  int i;

  the_node = ocrm_table[id].nodes;
  index_upper_limit = 1 << (ocrm_table[id].max_deg+1);
  index_lower_limit = 1 << (ocrm_table[id].base_deg);

  if ( (serial < index_lower_limit) || (serial >= index_upper_limit) ) {
    fprintf(stderr, "ocrm_free_code: ..warning( invalid serial )!\n");
    return;
  }

  /* Enable the asignment of all direct decendents */
  {
    int i, j;
    int items_to_free;
      
    items_to_free = 2;
    for( i = serial << 1; i < index_upper_limit; i <<= 1, items_to_free <<= 1) {
      for ( j = 0; j < items_to_free; j++ ) {
	the_node[i+j].state   = FREE;
      }
    }
  }

  /* Enable the assignment of all direct ancestors
     if other decendents agree with that. */
  {
    int sibling; /* brother node */
    
    for ( i = serial; i >= index_lower_limit; i >>= 1 ) {
      the_node[i].state = FREE;
      sibling = ( i & 1 ) ? i - 1: i + 1;
      if ( the_node[sibling].state != FREE )
	break;
    }
  }
}

void ocrm_free_index ( int id, int deg, int index )
  /* It makes the code index available */
{
  OCodeNode *the_node;
  int min, max;
  int i;

  the_node = ocrm_table[id].nodes;
  min = 1 << deg;
  max = 1 << (deg+1);

  for ( i = min; i < max; i++ ) {
    if ( (the_node[i].state == USED) && (the_node[i].index == index) ){
      ocrm_free_code( id, i );
      return;
    }
  }
  fprintf(stderr, "ocrm_free_index: .. trying to free an unused code!\n");
}

void ocrm_print_tree( int id )
  /* This prints all the information for the tree. */
{
  OCodeNode *the_nodes;
  int  deg;
  int  min, max;
  int  i, j;
  char state;
  
  the_nodes = ocrm_table[id].nodes;
  for ( deg = ocrm_table[id].base_deg; deg <= ocrm_table[id].max_deg; deg++ ) {
    printf("%2d : ", deg);
    min = 1 << deg; max = 1 << (deg+1);
    for( i = min, j = 0; i < max; i++, j++ ) {
      switch( the_nodes[i].state ) {
      case FREE:
	state = 'F';
	break;
      case USED:
	state = 'U';
	break;
      case FORBIDDEN:
	state = 'D';
	break;
      default:
	state = 'X';
	break;
      }
      printf("%3d%c, ", the_nodes[i].index, state);
      if ( j == 15 ) {
	printf("\n     ");
	j = -1;
      }
    }
    puts("");
  }
}