website/archive/binaries/mac/src/muscle/bittraceback.cpp

   1 #include "muscle.h"\r
   2 #include "pwpath.h"\r
   3 \r
   4 #define TRACE 0\r
   5 \r
   6 static char XlatEdgeType(char c)\r
   7         {\r
   8         if ('E' == c)\r
   9                 return 'D';\r
  10         if ('J' == c)\r
  11                 return 'I';\r
  12         return c;\r
  13         }\r
  14 \r
  15 static const char *BitsToStr(char Bits)\r
  16         {\r
  17         static char Str[] = "xM xD xI";\r
  18 \r
  19         switch (Bits & BIT_xM)\r
  20                 {\r
  21         case BIT_MM:\r
  22                 Str[0] = 'M';\r
  23                 break;\r
  24         case BIT_DM:\r
  25                 Str[0] = 'D';\r
  26                 break;\r
  27         case BIT_IM:\r
  28                 Str[0] = 'I';\r
  29                 break;\r
  30                 }\r
  31 \r
  32         switch (Bits & BIT_xD)\r
  33                 {\r
  34         case BIT_MD:\r
  35                 Str[3] = 'M';\r
  36                 break;\r
  37         case BIT_DD:\r
  38                 Str[3] = 'D';\r
  39                 break;\r
  40                 }\r
  41 \r
  42         switch (Bits & BIT_xI)\r
  43                 {\r
  44         case BIT_MI:\r
  45                 Str[6] = 'M';\r
  46                 break;\r
  47         case BIT_II:\r
  48                 Str[6] = 'I';\r
  49                 break;\r
  50                 }\r
  51 \r
  52         return Str;\r
  53         }\r
  54 \r
  55 static inline char XChar(char Bits, char cType)\r
  56         {\r
  57         switch (cType)\r
  58                 {\r
  59         case 'M':\r
  60                 {\r
  61                 switch (Bits & BIT_xM)\r
  62                         {\r
  63                 case BIT_MM:\r
  64                         return 'M';\r
  65                 case BIT_DM:\r
  66                         return 'D';\r
  67                 case BIT_IM:\r
  68                         return 'I';\r
  69 #if     DOUBLE_AFFINE\r
  70                 case BIT_EM:\r
  71                         return 'E';\r
  72                 case BIT_JM:\r
  73                         return 'J';\r
  74 #endif\r
  75                         }\r
  76                 Quit("Huh!?");\r
  77                 return '?';\r
  78                 }\r
  79         case 'D':\r
  80                 {\r
  81                 switch (Bits & BIT_xD)\r
  82                         {\r
  83                 case BIT_MD:\r
  84                         return 'M';\r
  85                 case BIT_DD:\r
  86                         return 'D';\r
  87                         }\r
  88                 Quit("Huh!?");\r
  89                 return '?';\r
  90                 }\r
  91         case 'I':\r
  92                 {\r
  93                 switch (Bits & BIT_xI)\r
  94                         {\r
  95                 case BIT_MI:\r
  96                         return 'M';\r
  97                 case BIT_II:\r
  98                         return 'I';\r
  99                         }\r
 100                 Quit("Huh!?");\r
 101                 return '?';\r
 102                 }\r
 103 #if     DOUBLE_AFFINE\r
 104         case 'E':\r
 105                 {\r
 106                 switch (Bits & BIT_xE)\r
 107                         {\r
 108                 case BIT_ME:\r
 109                         return 'M';\r
 110                 case BIT_EE:\r
 111                         return 'E';\r
 112                         }\r
 113                 Quit("Huh!?");\r
 114                 return '?';\r
 115                 }\r
 116         case 'J':\r
 117                 {\r
 118                 switch (Bits & BIT_xJ)\r
 119                         {\r
 120                 case BIT_MJ:\r
 121                         return 'M';\r
 122                 case BIT_JJ:\r
 123                         return 'J';\r
 124                         }\r
 125                 Quit("Huh!?");\r
 126                 return '?';\r
 127                 }\r
 128 #endif\r
 129         default:\r
 130                 Quit("Huh?");\r
 131                 return '?';\r
 132                 }\r
 133         }\r
 134 \r
 135 void BitTraceBack(char **TraceBack, unsigned uLengthA, unsigned uLengthB,\r
 136   char LastEdge, PWPath &Path)\r
 137         {\r
 138 #if     TRACE\r
 139         Log("BitTraceBack\n");\r
 140 #endif\r
 141         Path.Clear();\r
 142 \r
 143         PWEdge Edge;\r
 144         Edge.uPrefixLengthA = uLengthA;\r
 145         Edge.uPrefixLengthB = uLengthB;\r
 146         char Bits = TraceBack[uLengthA][uLengthB];\r
 147         Edge.cType = LastEdge;\r
 148         for (;;)\r
 149                 {\r
 150 #if     TRACE\r
 151                 Log("Prepend %c%d.%d\n", Edge.cType, Edge.uPrefixLengthA, Edge.uPrefixLengthB);\r
 152 #endif\r
 153                 char cSave = Edge.cType;\r
 154                 Edge.cType = XlatEdgeType(cSave);\r
 155                 Path.PrependEdge(Edge);\r
 156                 Edge.cType = cSave;\r
 157 \r
 158                 unsigned PLA = Edge.uPrefixLengthA;\r
 159                 unsigned PLB = Edge.uPrefixLengthB;\r
 160                 char Bits = TraceBack[PLA][PLB];\r
 161                 char NextEdgeType = XChar(Bits, Edge.cType);\r
 162 #if     TRACE\r
 163                 Log("XChar(%s, %c) = %c\n", BitsToStr(Bits), Edge.cType, NextEdgeType);\r
 164 #endif\r
 165                 switch (Edge.cType)\r
 166                         {\r
 167                 case 'M':\r
 168                         {\r
 169                         if (Edge.uPrefixLengthA == 0)\r
 170                                 Quit("BitTraceBack MA=0");\r
 171                         if (Edge.uPrefixLengthB == 0)\r
 172                                 Quit("BitTraceBack MA=0");\r
 173                         --(Edge.uPrefixLengthA);\r
 174                         --(Edge.uPrefixLengthB);\r
 175                         break;\r
 176                         }\r
 177                 case 'D':\r
 178                 case 'E':\r
 179                         {\r
 180                         if (Edge.uPrefixLengthA == 0)\r
 181                                 Quit("BitTraceBack DA=0");\r
 182                         --(Edge.uPrefixLengthA);\r
 183                         break;\r
 184                         }\r
 185                 case 'I':\r
 186                 case 'J':\r
 187                         {\r
 188                         if (Edge.uPrefixLengthB == 0)\r
 189                                 Quit("BitTraceBack IB=0");\r
 190                         --(Edge.uPrefixLengthB);\r
 191                         break;\r
 192                         }\r
 193                 default:\r
 194                         Quit("BitTraceBack: Invalid edge %c", Edge);\r
 195                         }\r
 196 \r
 197                 if (0 == Edge.uPrefixLengthA && 0 == Edge.uPrefixLengthB)\r
 198                         break;\r
 199 \r
 200                 Edge.cType = NextEdgeType;\r
 201                 }\r
 202 \r
 203 #if     TRACE\r
 204         Path.LogMe();\r
 205 #endif\r
 206         }\r