1 /* K=9 r=1/2 Viterbi decoder for PowerPC G4/G5 Altivec 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 <sys/sysctl.h> 9 #include "fec.h" 10 11 typedef union { unsigned char c[256]; vector bool char v[16]; } decision_t; 12 typedef union { unsigned char c[256]; vector unsigned char v[16]; } metric_t; 13 14 static union branchtab29 { unsigned char c[128]; vector unsigned char v[8]; } Branchtab29[2]; 15 static int Init = 0; 16 17 /* State info for instance of Viterbi decoder */ 18 struct v29 { 19 metric_t metrics1; /* path metric buffer 1 */ 20 metric_t metrics2; /* path metric buffer 2 */ 21 decision_t *dp; /* Pointer to current decision */ 22 metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 23 decision_t *decisions; /* Beginning of decisions for block */ 24 }; 25 26 /* Initialize Viterbi decoder for start of new frame */ 27 int init_viterbi29_av(void *p,int starting_state){ 28 struct v29 *vp = p; 29 int i; 30 31 if(p == NULL) 32 return -1; 33 for(i=0;i<16;i++) 34 vp->metrics1.v[i] = (vector unsigned char)(63); 35 36 vp->old_metrics = &vp->metrics1; 37 vp->new_metrics = &vp->metrics2; 38 vp->dp = vp->decisions; 39 vp->old_metrics->c[starting_state & 255] = 0; /* Bias known start state */ 40 return 0; 41 } 42 43 void set_viterbi29_polynomial_av(int polys[2]){ 44 int state; 45 46 for(state=0;state < 128;state++){ 47 Branchtab29[0].c[state] = (polys[0] < 0) ^ parity((2*state) & abs(polys[0])) ? 255 : 0; 48 Branchtab29[1].c[state] = (polys[1] < 0) ^ parity((2*state) & abs(polys[1])) ? 255 : 0; 49 } 50 Init++; 51 } 52 53 /* Create a new instance of a Viterbi decoder */ 54 void *create_viterbi29_av(int len){ 55 struct v29 *vp; 56 57 if(!Init){ 58 int polys[2] = { V29POLYA,V29POLYB }; 59 set_viterbi29_polynomial_av(polys); 60 } 61 if((vp = (struct v29 *)malloc(sizeof(struct v29))) == NULL) 62 return NULL; 63 if((vp->decisions = (decision_t *)malloc((len+8)*sizeof(decision_t))) == NULL){ 64 free(vp); 65 return NULL; 66 } 67 init_viterbi29_av(vp,0); 68 return vp; 69 } 70 71 /* Viterbi chainback */ 72 int chainback_viterbi29_av( 73 void *p, 74 unsigned char *data, /* Decoded output data */ 75 unsigned int nbits, /* Number of data bits */ 76 unsigned int endstate){ /* Terminal encoder state */ 77 struct v29 *vp = p; 78 decision_t *d; 79 80 if(p == NULL) 81 return -1; 82 d = (decision_t *)vp->decisions; 83 /* Make room beyond the end of the encoder register so we can 84 * accumulate a full byte of decoded data 85 */ 86 endstate %= 256; 87 88 /* The store into data[] only needs to be done every 8 bits. 89 * But this avoids a conditional branch, and the writes will 90 * combine in the cache anyway 91 */ 92 d += 8; /* Look past tail */ 93 while(nbits-- != 0){ 94 int k; 95 96 k = d[nbits].c[endstate] & 1; 97 data[nbits>>3] = endstate = (endstate >> 1) | (k << 7); 98 } 99 return 0; 100 } 101 102 103 /* Delete instance of a Viterbi decoder */ 104 void delete_viterbi29_av(void *p){ 105 struct v29 *vp = p; 106 107 if(vp != NULL){ 108 free(vp->decisions); 109 free(vp); 110 } 111 } 112 113 114 int update_viterbi29_blk_av(void *p,unsigned char *syms,int nbits){ 115 struct v29 *vp = p; 116 decision_t *d; 117 int i; 118 119 if(p == NULL) 120 return -1; 121 d = (decision_t *)vp->dp; 122 123 while(nbits--){ 124 vector unsigned char sym1v,sym2v; 125 void *tmp; 126 127 /* All this seems necessary just to load a byte into all elements of a vector! */ 128 sym1v = vec_perm(vec_ld(0,syms),vec_ld(1,syms),vec_lvsl(0,syms)); /* sym1v.0 = syms[0]; sym1v.1 = syms[1] */ 129 sym2v = vec_splat(sym1v,1); /* Splat syms[1] across sym2v */ 130 sym1v = vec_splat(sym1v,0); /* Splat syms[0] across sym1v */ 131 syms += 2; 132 133 for(i=0;i<8;i++){ 134 vector bool char decision0,decision1; 135 vector unsigned char metric,m_metric,m0,m1,m2,m3,survivor0,survivor1; 136 137 /* Form branch metrics */ 138 metric = vec_avg(vec_xor(Branchtab29[0].v[i],sym1v),vec_xor(Branchtab29[1].v[i],sym2v)); 139 metric = vec_sr(metric,(vector unsigned char)(3)); 140 m_metric = (vector unsigned char)(31) - metric; 141 142 /* Add branch metrics to path metrics */ 143 m0 = vec_adds(vp->old_metrics->v[i],metric); 144 m3 = vec_adds(vp->old_metrics->v[8+i],metric); 145 m1 = vec_adds(vp->old_metrics->v[8+i],m_metric); 146 m2 = vec_adds(vp->old_metrics->v[i],m_metric); 147 148 /* Compare and select first set */ 149 decision0 = vec_cmpgt(m0,m1); 150 decision1 = vec_cmpgt(m2,m3); 151 survivor0 = vec_min(m0,m1); 152 survivor1 = vec_min(m2,m3); 153 154 /* Interleave and store decisions and survivors */ 155 d->v[2*i] = vec_mergeh(decision0,decision1); 156 d->v[2*i+1] = vec_mergel(decision0,decision1); 157 vp->new_metrics->v[2*i] = vec_mergeh(survivor0,survivor1); 158 vp->new_metrics->v[2*i+1] = vec_mergel(survivor0,survivor1); 159 } 160 d++; 161 /* renormalize if necessary */ 162 if(vp->new_metrics->c[0] >= 50){ 163 int i; 164 vector unsigned char scale0,scale1; 165 166 /* Find smallest metric and splat */ 167 scale0 = vp->new_metrics->v[0]; 168 scale1 = vp->new_metrics->v[1]; 169 for(i=2;i<16;i+=2){ 170 scale0 = vec_min(scale0,vp->new_metrics->v[i]); 171 scale1 = vec_min(scale1,vp->new_metrics->v[i+1]); 172 } 173 scale0 = vec_min(scale0,scale1); 174 scale0 = vec_min(scale0,vec_sld(scale0,scale0,8)); 175 scale0 = vec_min(scale0,vec_sld(scale0,scale0,4)); 176 scale0 = vec_min(scale0,vec_sld(scale0,scale0,2)); 177 scale0 = vec_min(scale0,vec_sld(scale0,scale0,1)); 178 179 /* Now subtract from all metrics */ 180 for(i=0;i<16;i++) 181 vp->new_metrics->v[i] = vec_subs(vp->new_metrics->v[i],scale0); 182 } 183 /* Swap pointers to old and new metrics */ 184 tmp = vp->old_metrics; 185 vp->old_metrics = vp->new_metrics; 186 vp->new_metrics = tmp; 187 } 188 vp->dp = d; 189 return 0; 190 } 191
