schro_parse.c

   1 #include <string.h>
   2
   3 #include <stdio.h>
   4
   5 #include <schroedinger/schro.h>
   6 #include <list>
   7
   8 enum SyncState {
   9         NOT_SYNCED=0,
  10         GOT_1PCP,
  11         TRY_SYNC,
  12         SYNCED,
  13         SYNCED_INCOMPLETEDU
  14 };
  15
  16 void operator++(SyncState& s) { s = (SyncState)(s+1); }
  17
  18 struct SchroSyncState {
  19         enum SyncState state;
  20         int last_npo;
  21         int offset;
  22         std::list <SchroBuffer*> bufs;
  23 };
  24
  25 static const char* syncstate_to_str[] = {
  26         "NOT_SYNCED", "GOT_1PCP", "TRY_SYNC", "SYNCED", "SYNCED_INCOMPLETEDU"
  27 };
  28
  29 typedef std::list<SchroBuffer*> BS;
  30
  31 /* search @bufs@, starting at @offset@ to (sum (map length bufs))-10
  32  * for a parse_code_prefix.
  33  *
  34  * The -10 is to avoid situations where a match would be found, but
  35  * there isn't a complete parse_code_prefix in the bufferlist.
  36  */
  37 bool schro_buflist_find_parseinfo(BS& bufs, int& offset)
  38 {
  39         BS::iterator it = bufs.begin();
  40         int idx = offset;
  41         int idx_offset = 0;
  42
  43         BS::iterator last = bufs.end();
  44         --last;
  45
  46         /* find starting buffer and offset into it */
  47         while (idx >= (*it)->length) {
  48                 idx -= (*it)->length;
  49                 idx_offset += (*it)->length;
  50                 ++it;
  51         }
  52
  53         do {
  54                 int endskip = (it == last) ? 10 : 0;
  55                 unsigned char* pos = (unsigned char*) memmem((*it)->data + idx, (*it)->length - idx - endskip, "BBCD", 4);
  56                 if (pos) {
  57                         /* found in this buffer */
  58                         offset = idx_offset + pos - (*it)->data;
  59                         return true;
  60                 }
  61
  62                 if (endskip)
  63                         break;
  64
  65                 /* deal with finding prefix that spans two buffers */
  66                 /* part (1) look in this buffer */
  67                 int i = 0;
  68                 for (i = 0; i < 3; i++) {
  69                         bool found = true;
  70                         for (int j = 0; j < 3-i; j++) {
  71                                 if ("BBCD"[j] != *((*it)->data + (*it)->length - 3 + i)) {
  72                                         found = false;
  73                                 }
  74                         }
  75                         if (found)
  76                                 break;
  77                 }
  78
  79                 idx = 0;
  80                 idx_offset += (*it)->length;
  81                 ++it;
  82
  83                 /* part (2) look in the next buffer */
  84                 for (int j = 0; j < 1+i; j++) {
  85                         if ("BBCD"[3-i+j] != *((*it)->data + j)) {
  86                                 offset = idx_offset + j;
  87                                 return true;
  88                         }
  89                 }
  90         } while (it != bufs.end());
  91         return false;
  92 }
  93
  94 int
  95 schro_buflist_length(BS& bufs)
  96 {
  97         int len = 0;
  98         for (BS::iterator it = bufs.begin(); it != bufs.end(); ++it)
  99                 len += (*it)->length;
 100         return len;
 101 }
 102
 103 SchroBuffer*
 104 schro_buflist_new_subbuffer(BS& bufs, int offset, int len)
 105 {
 106         BS::iterator it = bufs.begin();
 107         int idx = offset;
 108
 109         /* find starting buffer and offset into it */
 110         while (idx >= (*it)->length) {
 111                 idx -= (*it)->length;
 112                 ++it;
 113         }
 114
 115         if (idx + len <= (*it)->length) {
 116                 /* the found du is wholy in one buffer, form a subbuffer */
 117                 return schro_buffer_new_subbuffer(*it, idx, len);
 118         }
 119
 120         /* otherwise, aggregate to form a new buffer */
 121         SchroBuffer *b = schro_buffer_new_and_alloc(len);
 122         offset = 0;
 123         for (; it != bufs.end(); ++it, idx = 0) {
 124                 int blen = (*it)->length - idx;
 125                 int sublen = len < blen ? len : blen;
 126                 memcpy(b->data + offset, (*it)->data + idx, sublen);
 127                 offset += sublen;
 128                 len -= sublen;
 129                 if (!len)
 130                         return b;
 131         }
 132
 133         schro_buffer_unref(b);
 134         return NULL;
 135 }
 136
 137 struct ParseInfo {
 138         int32_t next_parse_offset;
 139         int32_t prev_parse_offset;
 140         int parse_code;
 141 };
 142
 143 bool schro_buflist_unpack_parseinfo(ParseInfo* pi, BS& bufs, int offset)
 144 {
 145         if (offset < 0)
 146                 return false;
 147
 148         BS::iterator it = bufs.begin();
 149         int idx = offset;
 150
 151         /* find starting buffer and offset into it */
 152         while (idx >= (*it)->length) {
 153                 idx -= (*it)->length;
 154                 ++it;
 155         }
 156
 157         const unsigned char* pu = (*it)->data + idx;
 158
 159         if ((*it)->length - idx > 13) {
 160                 /* fast path */
 161                 if (pu[0] != 'B' || pu[1] != 'B' || pu[2] != 'C' || pu[3] != 'D')
 162                         return false;
 163
 164                 pi->parse_code = pu[4];
 165                 pi->next_parse_offset = pu[5] << 24 | pu[6] << 16 | pu[7] << 8 | pu[8];
 166                 pi->prev_parse_offset = pu[9] << 24 | pu[10] << 16 | pu[11] << 8 | pu[12];
 167                 return true;
 168         }
 169
 170         /* slow path */
 171         memset(pi, 0, sizeof(ParseInfo));
 172         for (int i = 0; i < 13; i++) {
 173                 if (it == bufs.end())
 174                         return false;
 175
 176                 switch (i) {
 177                 case 0: case 1: case 2: case 3:
 178                         if (pu[i] != "BBCD"[i])
 179                                 return false;
 180                         break;
 181                 case 4:
 182                         pi->parse_code = pu[4];
 183                         break;
 184                 case 5: case 6: case 7: case 8:
 185                         pi->next_parse_offset |= pu[i] << ((8-i)*8);
 186                         break;
 187                 case 9: case 10: case 11: case 12:
 188                         pi->prev_parse_offset |= pu[i] << ((12-i)*8);
 189                         break;
 190                 }
 191
 192                 if (idx + i + 1 == (*it)->length) {
 193                         ++it;
 194                         idx = 0;
 195                         pu = (*it)->data - i -1;
 196                 }
 197         }
 198         /* slowpath complete */
 199         return true;
 200 }
 201
 202 SchroBuffer*
 203 schro_parse_getnextdu(SchroSyncState* s, SchroBuffer* b)
 204 {
 205         if (b)
 206                 s->bufs.push_back(b);
 207
 208         if (schro_buflist_length(s->bufs) == 0)
 209                 return NULL;
 210
 211         ParseInfo pu;
 212
 213         do {
 214                 switch (s->state) {
 215                 case NOT_SYNCED: /* -> GOT_1PCP */
 216                 case GOT_1PCP:   /* -> TRY_SYNC */
 217                         /* the only reason we care about 1PCP, is to stop reading
 218                          * a random stream filling up buf_list forever. (assuming
 219                          * that no 'BBCD' emulation occurs */
 220                         /* XXX, not handled yet */
 221                         if (schro_buflist_length(s->bufs) - s->offset <= 1)
 222                                 /* there must be at least one byte avaliable in bufs */
 223                                 return NULL;
 224                         s->offset++;
 225                         if (schro_buflist_find_parseinfo(s->bufs, s->offset))
 226                                 ++s->state;
 227                         break;
 228                 case TRY_SYNC: { /* -> (SYNCED | GOT_1PCP) */
 229                         ParseInfo pu1;
 230                         bool a = schro_buflist_unpack_parseinfo(&pu1, s->bufs, s->offset);
 231                         bool b = schro_buflist_unpack_parseinfo(&pu, s->bufs, s->offset - pu1.prev_parse_offset);
 232                         if (!a || !b || (pu1.prev_parse_offset != pu.next_parse_offset)) {
 233                                 s->state = GOT_1PCP;
 234                                 break;
 235                         }
 236                         s->last_npo = pu.next_parse_offset;
 237                         s->state = SYNCED;
 238                         break;
 239                 }
 240                 case SYNCED: {  /* -> (SYNCED | GOT_1PCP) */
 241                         bool a = schro_buflist_unpack_parseinfo(&pu, s->bufs, s->offset);
 242                         if (!a || (s->last_npo != pu.prev_parse_offset)) {
 243                                 s->state = GOT_1PCP;
 244                                 break;
 245                         }
 246                         s->offset += pu.next_parse_offset;
 247                         s->last_npo = pu.next_parse_offset;
 248                         s->state = SYNCED;
 249                         break;
 250                 }
 251                 case SYNCED_INCOMPLETEDU:
 252                         /* reread pi */
 253                         schro_buflist_unpack_parseinfo(&pu, s->bufs, s->offset - s->last_npo);
 254                         s->state = SYNCED; /* try again */
 255                 default: break;
 256                 }
 257         } while (SYNCED != s->state);
 258
 259         if (SYNCED != s->state)
 260                 return NULL;
 261
 262         /* synced, extract a data unit */
 263         SchroBuffer* du;
 264         du = schro_buflist_new_subbuffer(s->bufs
 265                                         ,s->offset - pu.next_parse_offset
 266                                         ,pu.next_parse_offset);
 267         if (!du) {
 268                 s->state = SYNCED_INCOMPLETEDU;
 269                 return NULL;
 270         }
 271
 272 #if 0
 273                 fprintf(stderr, "got: (from offset:%d len:%d\n"
 274                        " %02x %02x %02x %02x\n %02x\n"
 275                        " %02x %02x %02x %02x\n %02x %02x %02x %02x\n"
 276                        ,s->offset - pu.next_parse_offset, pu.next_parse_offset
 277                        ,du->data[0], du->data[1], du->data[2], du->data[3]
 278                        ,du->data[4]
 279                        ,du->data[5], du->data[6], du->data[7], du->data[8]
 280                        ,du->data[9], du->data[10], du->data[11], du->data[12]
 281                        );
 282 #endif
 283         /* clean up bufs */
 284         /* see if offset is > any buffers in buf */
 285         for (BS::iterator it = s->bufs.begin(); it != s->bufs.end();) {
 286                 if ((*it)->length > s->offset)
 287                         break;
 288                 s->offset -= (*it)->length;
 289                 ++it;
 290                 b = s->bufs.front();
 291                 schro_buffer_unref(b);
 292                 s->bufs.pop_front();
 293         }
 294
 295         return du;
 296 }