1 /* K=9 r=1/3 Viterbi decoder in portable C 2 * Copyright Aug 2006, Phil Karn, KA9Q 3 * May be used under the terms of the GNU Lesser General Public License (LGPL) 4 */ 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <memory.h> 8 #include "fec.h" 9 10 typedef union { unsigned int w[256]; } metric_t; 11 typedef union { unsigned long w[8];} decision_t; 12 13 static union { unsigned char c[128]; } Branchtab39[3]; 14 static int Init = 0; 15 16 /* State info for instance of Viterbi decoder */ 17 struct v39 { 18 metric_t metrics1; /* path metric buffer 1 */ 19 metric_t metrics2; /* path metric buffer 2 */ 20 decision_t *dp; /* Pointer to current decision */ 21 metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 22 decision_t *decisions; /* Beginning of decisions for block */ 23 }; 24 25 /* Initialize Viterbi decoder for start of new frame */ 26 int init_viterbi39_port(void *p,int starting_state){ 27 struct v39 *vp = p; 28 int i; 29 30 if(p == NULL) 31 return -1; 32 for(i=0;i<256;i++) 33 vp->metrics1.w[i] = 63; 34 35 vp->old_metrics = &vp->metrics1; 36 vp->new_metrics = &vp->metrics2; 37 vp->dp = vp->decisions; 38 vp->old_metrics->w[starting_state & 255] = 0; /* Bias known start state */ 39 return 0; 40 } 41 42 void set_viterbi39_polynomial_port(int polys[3]){ 43 int state; 44 45 for(state=0;state < 128;state++){ 46 Branchtab39[0].c[state] = (polys[0] < 0) ^ parity((2*state) & abs(polys[0])) ? 255 : 0; 47 Branchtab39[1].c[state] = (polys[1] < 0) ^ parity((2*state) & abs(polys[1])) ? 255 : 0; 48 Branchtab39[2].c[state] = (polys[2] < 0) ^ parity((2*state) & abs(polys[2])) ? 255 : 0; 49 } 50 Init++; 51 } 52 53 /* Create a new instance of a Viterbi decoder */ 54 void *create_viterbi39_port(int len){ 55 struct v39 *vp; 56 57 if(!Init){ 58 int polys[3] = {V39POLYA,V39POLYB,V39POLYC}; 59 set_viterbi39_polynomial_port(polys); 60 } 61 if((vp = (struct v39 *)malloc(sizeof(struct v39))) == NULL) 62 return NULL; 63 64 if((vp->decisions = (decision_t *)malloc((len+8)*sizeof(decision_t))) == NULL){ 65 free(vp); 66 return NULL; 67 } 68 init_viterbi39_port(vp,0); 69 70 return vp; 71 } 72 73 74 /* Viterbi chainback */ 75 int chainback_viterbi39_port( 76 void *p, 77 unsigned char *data, /* Decoded output data */ 78 unsigned int nbits, /* Number of data bits */ 79 unsigned int endstate){ /* Terminal encoder state */ 80 struct v39 *vp = p; 81 decision_t *d; 82 83 if(p == NULL) 84 return -1; 85 86 d = vp->decisions; 87 /* Make room beyond the end of the encoder register so we can 88 * accumulate a full byte of decoded data 89 */ 90 endstate %= 256; 91 92 /* The store into data[] only needs to be done every 8 bits. 93 * But this avoids a conditional branch, and the writes will 94 * combine in the cache anyway 95 */ 96 d += 8; /* Look past tail */ 97 while(nbits-- != 0){ 98 int k; 99 100 k = (d[nbits].w[(endstate)/32] >> (endstate%32)) & 1; 101 data[nbits>>3] = endstate = (endstate >> 1) | (k << 7); 102 } 103 return 0; 104 } 105 106 107 /* Delete instance of a Viterbi decoder */ 108 void delete_viterbi39_port(void *p){ 109 struct v39 *vp = p; 110 111 if(vp != NULL){ 112 free(vp->decisions); 113 free(vp); 114 } 115 } 116 117 /* C-language butterfly */ 118 #define BFLY(i) {\ 119 unsigned int metric,m0,m1,decision;\ 120 metric = (Branchtab39[0].c[i] ^ sym0) + (Branchtab39[1].c[i] ^ sym1) + \ 121 (Branchtab39[2].c[i] ^ sym2);\ 122 m0 = vp->old_metrics->w[i] + metric;\ 123 m1 = vp->old_metrics->w[i+128] + (765 - metric);\ 124 decision = (signed int)(m0-m1) > 0;\ 125 vp->new_metrics->w[2*i] = decision ? m1 : m0;\ 126 d->w[i/16] |= decision << ((2*i)&31);\ 127 m0 -= (metric+metric-765);\ 128 m1 += (metric+metric-765);\ 129 decision = (signed int)(m0-m1) > 0;\ 130 vp->new_metrics->w[2*i+1] = decision ? m1 : m0;\ 131 d->w[i/16] |= decision << ((2*i+1)&31);\ 132 } 133 134 /* Update decoder with a block of demodulated symbols 135 * Note that nbits is the number of decoded data bits, not the number 136 * of symbols! 137 */ 138 139 int update_viterbi39_blk_port(void *p,unsigned char *syms,int nbits){ 140 struct v39 *vp = p; 141 decision_t *d; 142 143 if(p == NULL) 144 return -1; 145 146 d = (decision_t *)vp->dp; 147 while(nbits--){ 148 void *tmp; 149 unsigned char sym0,sym1,sym2; 150 int i; 151 152 for(i=0;i<8;i++) 153 d->w[i] = 0; 154 sym0 = *syms++; 155 sym1 = *syms++; 156 sym2 = *syms++; 157 158 for(i=0;i<128;i++) 159 BFLY(i); 160 161 d++; 162 tmp = vp->old_metrics; 163 vp->old_metrics = vp->new_metrics; 164 vp->new_metrics = tmp; 165 } 166 vp->dp = d; 167 return 0; 168 } 169