uchime_src/tracebackbit.cpp

   1 #include "dp.h"
   2
   3 #define TRACE   0
   4
   5 Mx<byte> g_Mx_TBBit;
   6 byte **g_TBBit;
   7 float *g_DPRow1;
   8 float *g_DPRow2;
   9 static float *g_DPBuffer1;
  10 static float *g_DPBuffer2;
  11
  12 static unsigned g_CacheLB;
  13
  14 void AllocBit(unsigned LA, unsigned LB)
  15         {
  16         g_Mx_TBBit.Alloc("TBBit", LA+1, LB+1);
  17         g_TBBit = g_Mx_TBBit.GetData();
  18         if (LB > g_CacheLB)
  19                 {
  20                 MYFREE(g_DPBuffer1, g_CacheLB, AllocBit);
  21                 MYFREE(g_DPBuffer2, g_CacheLB, AllocBit);
  22
  23                 g_CacheLB = LB + 128;
  24
  25         // Allow use of [-1]
  26                 //g_DPBuffer1 = myalloc<float>(g_CacheLB+3);
  27                 //g_DPBuffer2 = myalloc<float>(g_CacheLB+3);
  28                 g_DPBuffer1 = MYALLOC(float, g_CacheLB+3, AllocBit);
  29                 g_DPBuffer2 = MYALLOC(float, g_CacheLB+3, AllocBit);
  30                 g_DPRow1 = g_DPBuffer1 + 1;
  31                 g_DPRow2 = g_DPBuffer2 + 1;
  32                 }
  33         }
  34
  35 void TraceBackBit(unsigned LA, unsigned LB, char State, PathData &PD)
  36         {
  37         PD.Alloc(LA+LB);
  38
  39         StartTimer(TraceBackBit);
  40         char *PathPtr = PD.Back;
  41         *PathPtr = 0;
  42
  43         byte **TB = g_TBBit;
  44
  45 #if     TRACE
  46         Log("\n");
  47         Log("TraceBackBit\n");
  48 #endif
  49
  50         size_t i = LA;
  51         size_t j = LB;
  52         for (;;)
  53                 {
  54 #if     TRACE
  55                 Log("i=%3d  j=%3d  state=%c\n", (int) i, (int) j, State);
  56 #endif
  57                 if (i == 0 && j == 0)
  58                         break;
  59
  60                 --PathPtr;
  61                 *PathPtr = State;
  62
  63                 byte t;
  64                 switch (State)
  65                         {
  66                 case 'M':
  67                         asserta(i > 0 && j > 0);
  68                         t = TB[i-1][j-1];
  69                         if (t & TRACEBITS_DM)
  70                                 State = 'D';
  71                         else if (t & TRACEBITS_IM)
  72                                 State = 'I';
  73                         else
  74                                 State = 'M';
  75                         --i;
  76                         --j;
  77                         break;
  78                 case 'D':
  79                         asserta(i > 0);
  80                         t = TB[i-1][j];
  81                         if (t & TRACEBITS_MD)
  82                                 State = 'M';
  83                         else
  84                                 State = 'D';
  85                         --i;
  86                         break;
  87
  88                 case 'I':
  89                         asserta(j > 0);
  90                         t = TB[i][j-1];
  91                         if (t & TRACEBITS_MI)
  92                                 State = 'M';
  93                         else
  94                                 State = 'I';
  95                         --j;
  96                         break;
  97
  98                 default:
  99                         Die("TraceBackBit, invalid state %c", State);
 100                         }
 101                 }
 102         PD.Start = PathPtr;
 103         EndTimer(TraceBackBit);
 104         }
 105
 106 void TraceBackBitSW(unsigned LA, unsigned LB, unsigned Besti, unsigned Bestj,
 107   unsigned &Leni, unsigned &Lenj, PathData &PD)
 108         {
 109         PD.Alloc(LA+LB);
 110
 111         StartTimer(TraceBackBitSW);
 112         char *PathPtr = PD.Back;
 113         *PathPtr = 0;
 114
 115         byte **TB = g_TBBit;
 116
 117 #if     TRACE
 118         Log("\n");
 119         Log("TraceBackBitSW\n");
 120 #endif
 121
 122         unsigned i = Besti;
 123         unsigned j = Bestj;
 124         char State = 'M';
 125         for (;;)
 126                 {
 127 #if     TRACE
 128                 Log("i=%3d  j=%3d  state=%c\n", (int) i, (int) j, State);
 129 #endif
 130                 --PathPtr;
 131                 *PathPtr = State;
 132
 133                 byte t;
 134                 switch (State)
 135                         {
 136                 case 'M':
 137                         asserta(i > 0 && j > 0);
 138                         t = TB[i-1][j-1];
 139                         if (t & TRACEBITS_DM)
 140                                 State = 'D';
 141                         else if (t & TRACEBITS_IM)
 142                                 State = 'I';
 143                         else if (t & TRACEBITS_SM)
 144                                 {
 145                                 Leni = Besti - i + 1;
 146                                 Lenj = Bestj - j + 1;
 147                                 PD.Start = PathPtr;
 148                                 EndTimer(TraceBackBitSW);
 149                                 return;
 150                                 }
 151                         else
 152                                 State = 'M';
 153                         --i;
 154                         --j;
 155                         break;
 156                 case 'D':
 157                         asserta(i > 0);
 158                         t = TB[i-1][j];
 159                         if (t & TRACEBITS_MD)
 160                                 State = 'M';
 161                         else
 162                                 State = 'D';
 163                         --i;
 164                         break;
 165
 166                 case 'I':
 167                         asserta(j > 0);
 168                         t = TB[i][j-1];
 169                         if (t & TRACEBITS_MI)
 170                                 State = 'M';
 171                         else
 172                                 State = 'I';
 173                         --j;
 174                         break;
 175
 176                 default:
 177                         Die("TraceBackBitSW, invalid state %c", State);
 178                         }
 179                 }
 180         }