tracebackbit.cpp

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