1 /* K=7 r=1/2 Viterbi decoder in portable C 2 * Copyright Feb 2004, 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 <limits.h> 9 #include "fec.h" 10 11 12 typedef union { unsigned int w[64]; } metric_t; 13 typedef union { unsigned long w[2];} decision_t; 14 static union branchtab27 { unsigned char c[32]; } Branchtab27[2] __attribute__ ((aligned(16))); 15 static int Init = 0; 16 17 /* State info for instance of Viterbi decoder 18 * Don't change this without also changing references in [mmx|sse|sse2]bfly29.s! 19 */ 20 struct v27 { 21 metric_t metrics1; /* path metric buffer 1 */ 22 metric_t metrics2; /* path metric buffer 2 */ 23 decision_t *dp; /* Pointer to current decision */ 24 metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 25 decision_t *decisions; /* Beginning of decisions for block */ 26 }; 27 28 /* Initialize Viterbi decoder for start of new frame */ 29 int init_viterbi27_port(void *p,int starting_state){ 30 struct v27 *vp = p; 31 int i; 32 33 if(p == NULL) 34 return -1; 35 for(i=0;i<64;i++) 36 vp->metrics1.w[i] = 63; 37 38 vp->old_metrics = &vp->metrics1; 39 vp->new_metrics = &vp->metrics2; 40 vp->dp = vp->decisions; 41 vp->old_metrics->w[starting_state & 63] = 0; /* Bias known start state */ 42 return 0; 43 } 44 45 void set_viterbi27_polynomial_port(int polys[2]){ 46 int state; 47 48 for(state=0;state < 32;state++){ 49 Branchtab27[0].c[state] = (polys[0] < 0) ^ parity((2*state) & abs(polys[0])) ? 255 : 0; 50 Branchtab27[1].c[state] = (polys[1] < 0) ^ parity((2*state) & abs(polys[1])) ? 255 : 0; 51 } 52 Init++; 53 } 54 55 /* Create a new instance of a Viterbi decoder */ 56 void *create_viterbi27_port(int len){ 57 struct v27 *vp; 58 59 if(!Init){ 60 int polys[2] = { V27POLYA, V27POLYB }; 61 set_viterbi27_polynomial_port(polys); 62 } 63 if((vp = malloc(sizeof(struct v27))) == NULL) 64 return NULL; 65 if((vp->decisions = malloc((len+6)*sizeof(decision_t))) == NULL){ 66 free(vp); 67 return NULL; 68 } 69 init_viterbi27_port(vp,0); 70 71 return vp; 72 } 73 74 /* Viterbi chainback */ 75 int chainback_viterbi27_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 v27 *vp = p; 81 decision_t *d; 82 83 if(p == NULL) 84 return -1; 85 d = vp->decisions; 86 /* Make room beyond the end of the encoder register so we can 87 * accumulate a full byte of decoded data 88 */ 89 endstate %= 64; 90 endstate <<= 2; 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 += 6; /* Look past tail */ 97 while(nbits-- != 0){ 98 int k; 99 100 k = (d[nbits].w[(endstate>>2)/32] >> ((endstate>>2)%32)) & 1; 101 data[nbits>>3] = endstate = (endstate >> 1) | (k << 7); 102 } 103 return 0; 104 } 105 106 /* Delete instance of a Viterbi decoder */ 107 void delete_viterbi27_port(void *p){ 108 struct v27 *vp = p; 109 110 if(vp != NULL){ 111 free(vp->decisions); 112 free(vp); 113 } 114 } 115 116 /* C-language butterfly */ 117 #define BFLY(i) {\ 118 unsigned int metric,m0,m1,decision;\ 119 metric = (Branchtab27[0].c[i] ^ sym0) + (Branchtab27[1].c[i] ^ sym1);\ 120 m0 = vp->old_metrics->w[i] + metric;\ 121 m1 = vp->old_metrics->w[i+32] + (510 - metric);\ 122 decision = (signed int)(m0-m1) > 0;\ 123 vp->new_metrics->w[2*i] = decision ? m1 : m0;\ 124 d->w[i/16] |= decision << ((2*i)&31);\ 125 m0 -= (metric+metric-510);\ 126 m1 += (metric+metric-510);\ 127 decision = (signed int)(m0-m1) > 0;\ 128 vp->new_metrics->w[2*i+1] = decision ? m1 : m0;\ 129 d->w[i/16] |= decision << ((2*i+1)&31);\ 130 } 131 132 /* Update decoder with a block of demodulated symbols 133 * Note that nbits is the number of decoded data bits, not the number 134 * of symbols! 135 */ 136 int update_viterbi27_blk_port(void *p,unsigned char *syms,int nbits){ 137 struct v27 *vp = p; 138 void *tmp; 139 decision_t *d; 140 141 if(p == NULL) 142 return -1; 143 d = (decision_t *)vp->dp; 144 while(nbits--){ 145 unsigned char sym0,sym1; 146 147 d->w[0] = d->w[1] = 0; 148 sym0 = *syms++; 149 sym1 = *syms++; 150 151 BFLY(0); 152 BFLY(1); 153 BFLY(2); 154 BFLY(3); 155 BFLY(4); 156 BFLY(5); 157 BFLY(6); 158 BFLY(7); 159 BFLY(8); 160 BFLY(9); 161 BFLY(10); 162 BFLY(11); 163 BFLY(12); 164 BFLY(13); 165 BFLY(14); 166 BFLY(15); 167 BFLY(16); 168 BFLY(17); 169 BFLY(18); 170 BFLY(19); 171 BFLY(20); 172 BFLY(21); 173 BFLY(22); 174 BFLY(23); 175 BFLY(24); 176 BFLY(25); 177 BFLY(26); 178 BFLY(27); 179 BFLY(28); 180 BFLY(29); 181 BFLY(30); 182 BFLY(31); 183 d++; 184 /* Swap pointers to old and new metrics */ 185 tmp = vp->old_metrics; 186 vp->old_metrics = vp->new_metrics; 187 vp->new_metrics = tmp; 188 } 189 vp->dp = d; 190 return 0; 191 } 192
