ack.c

This a framework to test new ideas in transmission technology. Actual development is a LDPC-coder in

/***************************************************************************
 *    ack.c  -  Handle the acknowledge list
 *                           -------------------
 *   begin                :  2003
 *   authors              :  Linus Gasser
 *   emails               :  [e-mail]
 ***************************************************************************/

/***************************************************************************
 *                                Changes
 *                                -------
 * date - name - description
 * 03/05/05 - ineiti - start
 *
 **************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/


/* ------------------------------------------------------------------------
 * -----------------------------------------------------------------------*/

#include "system.h"
#include "ack.h"
#include "memory.h"
#include "debugging.h"

#define DBG_LVL 4


/**
 * @short initialise an acknowledge
 *
 * The first element of an acknowledge-array is used to do
 * some housekeeping. The len is the actual length, pos
 * is the next free ack and next is the next filled ack.
 *
 * @param a_ret where to store everything
 */
void ack_init( struct ack **a_ret ) {
  int i;
  struct ack *a;

  a = swr_malloc( MAX_ACK * sizeof( struct ack ) );
  a->pos  = 1;
  a->len = 0;
  a->next = 0;
  for ( i = 1; i < MAX_ACK; i++ ) {
    a[i].age = -1;
    a[i].next = 0;
  }
  *a_ret = a;
}


/**
 * @short clean up an ack-list
 */
void ack_free( struct ack **a_ret ) {
  swr_free( *a_ret );
}


/**
 * @short gets a free place
 *
 * Tries to find a free acknowledgement
 *
 * @return -1 for error else the index of the free place
 */
int ack_get_free( struct ack *a ) {
  int index;
  struct ack *p;

  index = a->pos;
  do {
    p = &a[ index ];
    if ( p->age < 0 ) {
      a->pos = index;
      a->len++;
      return index;
    }

    index = ( index + 1 ) % MAX_ACK;
    index += !index;
  } while ( index != a->pos );

  a->pos = index;
  PR_DBG( 0, "No place left in ack! This is bad\n" );
  return -1;
}


/**
 * @short insert a sorted acknowledge 
 *
 * Tries to insert an ack in the list in a sorted way.
 * The smallest elements come in first.
 */
int ack_ins_sorted( struct ack *a, int pos, int len ) {
  struct ack *p;
  int a_free, a_prev = 0, a_next = a->next,
                                   a_adj = 0;

  if ( a->len ) {
    p = &a[ a_next ];
    // Look for some wrap-over problems
    if ( ( p->pos < IP_BUF_LEN / 2 ) &&
         ( pos > IP_BUF_LEN / 2 ) ) {
      if ( p->pos + IP_BUF_LEN / 2 < pos ) {
        a_adj = IP_BUF_LEN;
      }
    } else if ( ( p->pos > IP_BUF_LEN / 2 ) &&
                ( pos < IP_BUF_LEN / 2 ) ) {
      if ( pos + IP_BUF_LEN / 2 < p->pos ) {
        a_adj = -IP_BUF_LEN;
      }
    }

    // Now search for our position
    while ( a_next && ( pos > p->pos + a_adj ) ) {
      a_prev = a_next;
      a_next = p->next;
      p = &a[ a_next ];
      if ( a[ a_prev ].pos > p->pos ) {
        // Wrap-around handling: if the actual position is
        // lower than the previous one, we have wrapped, so
        // we need to adjust a_adj
        a_adj += IP_BUF_LEN;
      }
    }
  }

  // Write to a free element and update the pointers and
  // counters
  a_free = ack_get_free( a );
  if ( a_free < 0 ) {
    return a_free;
  }

  p = &a[ a_free ];
  p->len = len;
  p->pos = pos;
  p->next = a_next;
  p->age = 0;
  a[ a_prev ].next = a_free;
  return 0;
}



/**
 * @short appends the ack to the end of the list
 */
int ack_append( struct ack *a, int pos, int len ) {
  int index;
  struct ack *p = a;

  index = ack_get_free( a );
  if ( index < 0 ) {
    return -1;
  }

  while ( p->next ) {
    p = a + p->next;
  };
  p->next = index;
  p = a + index;
  p->pos = pos;
  p->len = len;
  p->age = 0;
  p->next = 0;

  return 0;
}



/**
 * @short join blocks
 *
 * This function first joins all loose blocks and then returns
 * the first ack
 *
 * @param a the ack-list
 * @return the first ack
 */
struct ack *ack_join_blocks( struct ack *a ) {
  struct ack *a_curr, *a_next;

  if ( !a->len ) {
    return 0;
  }
  a_curr = &a[ a->next ];
  while ( a_curr->next ) {
    a_next = &a[ a_curr->next ];
    if ( ( a_curr->pos + a_curr->len ) % IP_BUF_LEN == a_next->pos ) {
      // Join two blocks
      a_curr->len += a_next->len;
      a_curr->next = a_next->next;
      a_next->next = 0;
      a_next->age = -1;
      a->len--;
    } else {
      // Get next block
      a_curr = a_next;
    }
  }
  return &a[ a->next ];
}


/*
 * @short cuts the first n bytes from the ack-list
 *
 * This is supposed to work on the rx-side of the RF, to
 * get one IP-packet. If the n-bytes correspond to exactly
 * the first packet, so it's size is only set to zero, w/o
 * removing it.
 *
 * @param a the ack-list
 * @param len the length of the packet to remove
 * @return index of where the first packet started, -1 on error
 */
int ack_cut_begin( struct ack *a, int len ) {
  int pos = -1;
  struct ack *p;

  if ( ( ack_join_blocks( a )->len >= len ) && ( len > 0 ) ) {
    p = &a[ a->next ];
    p->len -= len;
    pos = p->pos;
    p->pos = ( p->pos + len ) % IP_BUF_LEN;
  }
  return pos;
}


/**
 * @short delete the ack pos
 *
 * Searches for the ack with pos and deletes it
 *
 * @param a the ack-list
 * @param pos the position
 * @return 0 OK, -1 not found
 */
int ack_delete( struct ack *a, int pos ) {
  struct ack *p;
  int a_last = 0, a_next = 0;

  if ( !a->len ) {
    return -1;
  }

  a_next = a->next;
  do {
    p = &a[ a_next ];
    if ( p->pos == pos ) {
      // We found it
      a[ a_last ].next = p->next;
      p->next = 0;
      p->age = -1;
      a->len--;
      return 0;
    }

    // Not found (yet)
    a_last = a_next;
    a_next = p->next;
  } while ( a_next );

  // Didn't find at all
  return -1;
}


/**
 * @short gets the first ack and deletes it
 * 
 * @param a the ack-list
 * @return the ack or NULL for error
 */
struct ack *ack_get_first( struct ack *a ) {
  struct ack *p;

  if ( !a->len ) {
    return NULL;
  }

  p = &a[ a->next ];
  a->next = p->next;
  p->age = -1;
  a->len--;
  return p;
}


/**
 * @short returns the first ack
 * 
 * @param a the ack-list
 * @return the ack or NULL for error
 */
struct ack *ack_read_first( struct ack *a ) {
  struct ack *p;

  if ( !a->len ) {
    return NULL;
  }
  p = &a[ a->next ];
  return p;
}


/**
 * @short make the acks older
 *
 * @param a the ack-list
 */
void ack_make_older( struct ack *a ) {
  struct ack *p = a;

  if ( !a->len ) {
    return;
  }
  do {
    p = a + p->next;
    p->age++;
  } while ( p->next );
}


/**
 * @short returns an old ack
 *
 * Given an age, it returns the first ack found that has at
 * least this age, deletes it and returns a pointer.
 * If all acks are younger than the given age, NULL is returned.
 *
 * Care should be taken as the returned pointer may be re-used
 * on subsequent calls to ack_*.
 *
 * @param a the ack-list
 * @param age the maximal age
 * @return a pointer to an ack having at least this age or NULL
 */
struct ack *ack_delete_old( struct ack *a, int age ) {
  struct ack *t = a, *p;

  if ( !a->len ) {
    return NULL;
  }
  do {
    p = t;
    t = a + t->next;
    if ( t->age >= age ) {
      t->age = -1;
      p->next = t->next;
      return t;
    }
  } while ( p->next );
  return NULL;
}