1 /* K=15 r=1/6 Viterbi decoder for PowerPC G4/G5 Altivec vector instructions
2  * 8-bit offset-binary soft decision samples
3  * Copyright Mar 2004, Phil Karn, KA9Q
4  * May be used under the terms of the GNU Lesser General Public License (LGPL)
5  */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <memory.h>
9 #include <limits.h>
10 #include "fec.h"
11 
12 typedef union { unsigned char c[128][16]; vector unsigned char v[128]; } decision_t;
13 typedef union { unsigned short s[16384]; vector unsigned short v[2048]; } metric_t;
14 
15 static union branchtab615 { unsigned short s[8192]; vector unsigned short v[1024];} Branchtab615[6];
16 static int Init = 0;
17 
18 /* State info for instance of Viterbi decoder */
19 struct v615 {
20   metric_t metrics1; /* path metric buffer 1 */
21   metric_t metrics2; /* path metric buffer 2 */
22   void *dp;          /* Pointer to current decision */
23   metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */
24   void *decisions;   /* Beginning of decisions for block */
25 };
26 
27 /* Initialize Viterbi decoder for start of new frame */
init_viterbi615_av(void * p,int starting_state)28 int init_viterbi615_av(void *p,int starting_state){
29   struct v615 *vp = p;
30   int i;
31 
32   if(p == NULL)
33     return -1;
34 
35   for(i=0;i<2048;i++)
36     vp->metrics1.v[i] = (vector unsigned short)(5000);
37 
38   vp->old_metrics = &vp->metrics1;
39   vp->new_metrics = &vp->metrics2;
40   vp->dp = vp->decisions;
41   vp->old_metrics->s[starting_state & 16383] = 0; /* Bias known start state */
42   return 0;
43 }
44 
45 /* Create a new instance of a Viterbi decoder */
create_viterbi615_av(int len)46 void *create_viterbi615_av(int len){
47   struct v615 *vp;
48 
49   if(!Init){
50     int polys[6] = { V615POLYA,V615POLYB,V615POLYC,V615POLYD,V615POLYE,V615POLYF };
51     set_viterbi615_polynomial_av(polys);
52   }
53   vp = (struct v615 *)malloc(sizeof(struct v615));
54   vp->decisions = malloc(sizeof(decision_t)*(len+14));
55   init_viterbi615_av(vp,0);
56   return vp;
57 }
58 
set_viterbi615_polynomial_av(int polys[6])59 void set_viterbi615_polynomial_av(int polys[6]){
60   int state;
61   int i;
62 
63   for(state=0;state < 8192;state++){
64     for(i=0;i<6;i++)
65       Branchtab615[i].s[state] = (polys[i] < 0) ^ parity((2*state) & abs(polys[i])) ? 255 : 0;
66   }
67   Init++;
68 }
69 
70 
71 /* Viterbi chainback */
chainback_viterbi615_av(void * p,unsigned char * data,unsigned int nbits,unsigned int endstate)72 int chainback_viterbi615_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 v615 *vp = p;
78   decision_t *d = (decision_t *)vp->decisions;
79   int path_metric;
80 
81   endstate %= 16384;
82 
83   path_metric = vp->old_metrics->s[endstate];
84 
85   /* The store into data[] only needs to be done every 8 bits.
86    * But this avoids a conditional branch, and the writes will
87    * combine in the cache anyway
88    */
89   d += 14; /* Look past tail */
90   while(nbits-- != 0){
91     int k;
92 
93     k = (d[nbits].c[endstate >> 7][endstate & 15] & (0x80 >> ((endstate>>4)&7)) ) ? 1 : 0;
94     endstate = (k << 13) | (endstate >> 1);
95     data[nbits>>3] = endstate >> 6;
96   }
97   return path_metric;
98 }
99 
100 /* Delete instance of a Viterbi decoder */
delete_viterbi615_av(void * p)101 void delete_viterbi615_av(void *p){
102   struct v615 *vp = p;
103 
104   if(vp != NULL){
105     free(vp->decisions);
106     free(vp);
107   }
108 }
109 
update_viterbi615_blk_av(void * p,unsigned char * syms,int nbits)110 int update_viterbi615_blk_av(void *p,unsigned char *syms,int nbits){
111   struct v615 *vp = p;
112   decision_t *d = (decision_t *)vp->dp;
113   int path_metric = 0;
114   vector unsigned char decisions = (vector unsigned char)(0);
115 
116   while(nbits--){
117     vector unsigned short symv,sym0v,sym1v,sym2v,sym3v,sym4v,sym5v;
118     vector unsigned char s;
119     void *tmp;
120     int i;
121 
122     /* Splat the 0th symbol across sym0v, the 1st symbol across sym1v, etc */
123     s = (vector unsigned char)vec_perm(vec_ld(0,syms),vec_ld(5,syms),vec_lvsl(0,syms));
124 
125     symv = (vector unsigned short)vec_mergeh((vector unsigned char)(0),s);    /* Unsigned byte->word unpack */
126     sym0v = vec_splat(symv,0);
127     sym1v = vec_splat(symv,1);
128     sym2v = vec_splat(symv,2);
129     sym3v = vec_splat(symv,3);
130     sym4v = vec_splat(symv,4);
131     sym5v = vec_splat(symv,5);
132     syms += 6;
133 
134     for(i=0;i<1024;i++){
135       vector bool short decision0,decision1;
136       vector unsigned short metric,m_metric,m0,m1,m2,m3,survivor0,survivor1;
137 
138       /* Form branch metrics
139        * Because Branchtab takes on values 0 and 255, and the values of sym?v are offset binary in the range 0-255,
140        * the XOR operations constitute conditional negation.
141        * metric and m_metric (-metric) are in the range 0-1530
142        */
143       m0 = vec_add(vec_xor(Branchtab615[0].v[i],sym0v),vec_xor(Branchtab615[1].v[i],sym1v));
144       m1 = vec_add(vec_xor(Branchtab615[2].v[i],sym2v),vec_xor(Branchtab615[3].v[i],sym3v));
145       m2 = vec_add(vec_xor(Branchtab615[4].v[i],sym4v),vec_xor(Branchtab615[5].v[i],sym5v));
146       metric = vec_add(m0,m1);
147       metric = vec_add(metric,m2);
148       m_metric = vec_sub((vector unsigned short)(1530),metric);
149 
150       /* Add branch metrics to path metrics */
151       m0 = vec_adds(vp->old_metrics->v[i],metric);
152       m3 = vec_adds(vp->old_metrics->v[1024+i],metric);
153       m1 = vec_adds(vp->old_metrics->v[1024+i],m_metric);
154       m2 = vec_adds(vp->old_metrics->v[i],m_metric);
155 
156       /* Compare and select */
157       decision0 = vec_cmpgt(m0,m1);
158       decision1 = vec_cmpgt(m2,m3);
159       survivor0 = vec_min(m0,m1);
160       survivor1 = vec_min(m2,m3);
161 
162       /* Store decisions and survivors.
163        * To save space without SSE2's handy PMOVMSKB instruction, we pack and store them in
164        * a funny interleaved fashion that we undo in the chainback function.
165        */
166       decisions = vec_add(decisions,decisions); /* Shift each byte 1 bit to the left */
167 
168       /* Booleans are either 0xff or 0x00. Subtracting 0x00 leaves the lsb zero; subtracting
169        * 0xff is equivalent to adding 1, which sets the lsb.
170        */
171       decisions = vec_sub(decisions,(vector unsigned char)vec_pack(vec_mergeh(decision0,decision1),vec_mergel(decision0,decision1)));
172 
173       vp->new_metrics->v[2*i] = vec_mergeh(survivor0,survivor1);
174       vp->new_metrics->v[2*i+1] = vec_mergel(survivor0,survivor1);
175 
176       if((i % 8) == 7){
177 	/* We've accumulated a total of 128 decisions, stash and start again */
178 	d->v[i>>3] = decisions; /* No need to clear, the new bits will replace the old */
179       }
180     }
181 #if 0
182     /* Experimentally determine metric spread
183      * The results are fixed for a given code and input symbol size
184      */
185     {
186       int i;
187       vector unsigned short min_metric;
188       vector unsigned short max_metric;
189       union { vector unsigned short v; unsigned short s[8];} t;
190       int minimum,maximum;
191       static int max_spread = 0;
192 
193       min_metric = max_metric = vp->new_metrics->v[0];
194       for(i=1;i<2048;i++){
195 	min_metric = vec_min(min_metric,vp->new_metrics->v[i]);
196 	max_metric = vec_max(max_metric,vp->new_metrics->v[i]);
197       }
198       min_metric = vec_min(min_metric,vec_sld(min_metric,min_metric,8));
199       max_metric = vec_max(max_metric,vec_sld(max_metric,max_metric,8));
200       min_metric = vec_min(min_metric,vec_sld(min_metric,min_metric,4));
201       max_metric = vec_max(max_metric,vec_sld(max_metric,max_metric,4));
202       min_metric = vec_min(min_metric,vec_sld(min_metric,min_metric,2));
203       max_metric = vec_max(max_metric,vec_sld(max_metric,max_metric,2));
204 
205       t.v = min_metric;
206       minimum = t.s[0];
207       t.v = max_metric;
208       maximum = t.s[0];
209       if(maximum-minimum > max_spread){
210 	max_spread = maximum-minimum;
211 	printf("metric spread = %d\n",max_spread);
212       }
213     }
214 #endif
215 
216     /* Renormalize if necessary. This deserves some explanation.
217 
218      * The maximum possible spread, found by experiment, for 4-bit symbols is 405; for 8 bit symbols, it's 12750.
219      * So by looking at one arbitrary metric we can tell if any of them have possibly saturated.
220      * However, this is very conservative. Large spreads occur only at very high Eb/No, where
221      * saturating a bad path metric doesn't do much to increase its chances of being erroneously chosen as a survivor.
222 
223      * At more interesting (low) Eb/No ratios, the spreads are much smaller so our chances of saturating a metric
224      * by not not normalizing when we should are extremely low. So either way, the risk to performance is small.
225 
226      * All this is borne out by experiment.
227      */
228     if(vp->new_metrics->s[0] >= USHRT_MAX-12750){
229       vector unsigned short scale;
230       union { vector unsigned short v; unsigned short s[8];} t;
231 
232       /* Find smallest metric and splat */
233       scale = vp->new_metrics->v[0];
234       for(i=1;i<2048;i++)
235 	scale = vec_min(scale,vp->new_metrics->v[i]);
236 
237       scale = vec_min(scale,vec_sld(scale,scale,8));
238       scale = vec_min(scale,vec_sld(scale,scale,4));
239       scale = vec_min(scale,vec_sld(scale,scale,2));
240 
241       /* Subtract it from all metrics
242        * Work backwards to try to improve the cache hit ratio, assuming LRU
243        */
244       for(i=2047;i>=0;i--)
245 	vp->new_metrics->v[i] = vec_subs(vp->new_metrics->v[i],scale);
246       t.v = scale;
247       path_metric += t.s[0];
248     }
249     d++;
250     /* Swap pointers to old and new metrics */
251     tmp = vp->old_metrics;
252     vp->old_metrics = vp->new_metrics;
253     vp->new_metrics = tmp;
254   }
255   vp->dp = d;
256   return path_metric;
257 }
258