Debug and optimise C znc parser

1 files changed, 125 insertions, 136 deletions

diff --git a/cbits/znc.c b/cbits/znc.c
index 5bac7fd..3647395 100644
--- a/cbits/znc.c
+++ b/cbits/znc.c
@@ -6,13 +6,12 @@
 #include <assert.h>
 #include <emmintrin.h>
 
-// TODO: this still setfaults
-// $ cre tirclogv
-// *Main> :m *ZNC2
-// *ZNC2> :seti -XOverloadedStrings
-// *ZNC2> parseLog "[12:34:56] <nick> hoi!"
-// Error: [Cabal-7125]
-// repl failed for exe:tirclogv from tirclogv-0.1.0.0. The build process segfaulted (i.e. SIGSEGV).
+#if 0
+#include <stdio.h>
+#define DEBUG(...) fprintf(stderr, "[znc2] " __VA_ARGS__)
+#else
+#define DEBUG(...)
+#endif
 
 
 struct scanner {
@@ -22,17 +21,17 @@ struct scanner {
 };
 
 enum event_kind {
-  JOIN = 0,
-  PART = 1,
-  QUIT = 2,
-  RENICK = 3,
-  TALK = 4,
-  NOTICE = 5,
-  ACT = 6,
-  KICK = 7,
-  MODE = 8,
-  TOPIC = 9,
-  PARSEERROR = 10,
+  PARSEERROR = 0,
+  JOIN = 1,
+  PART = 2,
+  QUIT = 3,
+  RENICK = 4,
+  TALK = 5,
+  NOTICE = 6,
+  ACT = 7,
+  KICK = 8,
+  MODE = 9,
+  TOPIC = 10,
 };
 
 #pragma pack(1)
@@ -43,6 +42,24 @@ struct event {
   uint16_t len1, len2, len3;
 };
 
+static inline bool isdigit_char(char c) {
+  return c >= '0' && c <= '9';
+}
+
+// Exists to avoid UB by strict aliasing rule
+static inline uint32_t load_uint32(const char *ptr) {
+  uint32_t val;
+  memcpy(&val, ptr, 4);
+  return val;
+}
+
+// Exists to avoid UB by strict aliasing rule
+static inline uint64_t load_uint64(const char *ptr) {
+  uint64_t val;
+  memcpy(&val, ptr, 8);
+  return val;
+}
+
 // parses "[HH:MM:SS] " including the trailing space
 static bool parse_hms(struct scanner *s, struct event *dest) {
   const char *const loc = &s->buf[s->cur];
@@ -73,6 +90,15 @@ static inline bool eat_bytes(struct scanner *s, const char *tok, size_t toklen)
 
 #define EAT_BYTES(scanner_, tok_) eat_bytes(scanner_, tok_, strlen(tok_))
 
+static void skip_until(struct scanner *s, char delim) {
+  const char *const buf = s->buf;
+  const size_t len = s->len;
+  const size_t cur = s->cur;
+  const char *p = memchr(buf + cur, delim, len - cur);
+  if (p == NULL) s->cur = len;
+  else s->cur = p - buf;
+}
+
 static bool parse_nick(struct scanner *s, uint32_t *destptr, uint16_t *destlen) {
   // Delimiter bytes:
   // \t \n \v \r SP <  >
@@ -88,14 +114,14 @@ static bool parse_nick(struct scanner *s, uint32_t *destptr, uint16_t *destlen)
   const size_t startcur = s->cur;
   size_t cur = startcur;
 
-  while (cur + 4 <= len && (*(uint32_t*)&buf[cur] & 0x40404040U) == 0x40404040U) cur += 4;
-  while (cur < len && (buf[cur] & 0x40) == 0) cur++;
+  while (cur < len && (buf[cur] & 0x40) == 0x40) cur++;
   while (cur < len &&
       buf[cur] != '\t' && buf[cur] != '\n' && buf[cur] != '\v' && buf[cur] != '\r' &&
       buf[cur] != ' ' && buf[cur] != '<' && buf[cur] != '>')
     cur++;
 
   if (cur == startcur) return false;
+  if ((uint16_t)(cur - startcur) != cur - startcur) return false;
   *destptr = startcur;
   *destlen = cur - startcur;
   s->cur = cur;
@@ -107,24 +133,15 @@ static bool parse_inside_parens(struct scanner *s, uint32_t *destptr, uint16_t *
   const size_t len = s->len;
   size_t cur = s->cur;
 
-  if (cur + 2 >= len) return false;
+  if (cur + 1 >= len) return false;
   if (buf[cur] != '(') return false;
   cur++;
   const size_t startcur = cur;
 
   if (len - cur < 16) goto tail_loop;
 
-  {
-    const int nunaligned = (16 - (uintptr_t)(buf + cur) % 16) % 16;
-    for (int i = 0; i < nunaligned; i++, cur++) {
-      if (buf[cur] == ')') goto close_found;
-      if (buf[cur] == '\n') return false;
-    }
-  }
-
-  // now that we're aligned:
   while (cur + 16 <= len) {
-    const __m128i vec = _mm_load_si128((const __m128i*)(buf + cur));
+    const __m128i vec = _mm_loadu_si128((const __m128i*)(buf + cur));
     if (_mm_movemask_epi8(_mm_cmpeq_epi8(vec, _mm_set1_epi8(')' ))) != 0) break;
     if (_mm_movemask_epi8(_mm_cmpeq_epi8(vec, _mm_set1_epi8('\n'))) != 0) return false;
     cur += 16;
@@ -138,6 +155,7 @@ tail_loop:
   }
 
 close_found:
+  if ((uint16_t)(cur - startcur) != cur - startcur) return false;
   *destptr = startcur;
   *destlen = cur - startcur;
   s->cur = cur + 1;  // skip the closing paren
@@ -151,19 +169,20 @@ static bool parse_enclose_tail(
   const size_t len = s->len;
   size_t cur = s->cur;
 
-  if (cur + 2 >= len) return false;
+  if (cur + 1 >= len) return false;
   if (buf[cur] != leftdelim) return false;
   cur++;
   const size_t startcur = cur;
 
   const char *p = memchr(buf + cur, '\n', len - cur);
-  if (p == NULL) return false;
-  cur = p - (buf + cur);
+  if (p == NULL) cur = len;
+  else cur = p - buf;
 
   if (cur == startcur) return false;
   const size_t rightdelim_cur = cur - 1;
   if (buf[rightdelim_cur] != rightdelim) return false;
 
+  if ((uint16_t)(rightdelim_cur - startcur) != rightdelim_cur - startcur) return false;
   *destptr = startcur;
   *destlen = rightdelim_cur - startcur;
   s->cur = cur;  // skip the rightdelim, point to the newline
@@ -180,8 +199,9 @@ static bool parse_remaining(struct scanner *s, uint32_t *destptr, uint16_t *dest
   const size_t startcur = cur;
   const char *p = memchr(buf + cur, '\n', len - cur);
   if (p == NULL) return false;
-  cur = p - (buf + cur);
+  cur = p - buf;
 
+  if ((uint16_t)(cur - startcur) != cur - startcur) return false;
   *destptr = startcur;
   *destlen = cur - startcur;
   s->cur = cur;
@@ -191,18 +211,29 @@ static bool parse_remaining(struct scanner *s, uint32_t *destptr, uint16_t *dest
 // Assumes the "Joins: " etc. prefix has already been consumed
 static bool parse_useract(struct scanner *s, struct event *dest, bool withtail) {
   if (!parse_nick(s, &dest->ptr1, &dest->len1)) return false;
+  DEBUG(" parse_useract nick\n");
   if (!EAT_BYTES(s, " ")) return false;
+  DEBUG(" parse_useract space\n");
   if (!parse_inside_parens(s, &dest->ptr2, &dest->len2)) return false;
-  if (withtail)
+  DEBUG(" parse_useract parens\n");
+  if (withtail) {
+    if (!EAT_BYTES(s, " ")) return false;
+    DEBUG(" parse_useract space2\n");
     if (!parse_enclose_tail(s, &dest->ptr3, &dest->len3, '(', ')')) return false;
+    DEBUG(" parse_useract tail\n");
+  }
   return true;
 }
 
 static bool parse_eventdata(struct scanner *s, struct event *dest) {
+  DEBUG(" parse_eventdata cur=%zu\n", s->cur);
   if (EAT_BYTES(s, "*** ")) {
     if (EAT_BYTES(s, "Joins: ")) {
       dest->kind = JOIN;
-      return parse_useract(s, dest, false);
+      if (!parse_useract(s, dest, false)) return false;
+      // znc prints nickserv account name after parentheses since znc 1.9.0; skip it
+      skip_until(s, '\n');
+      return true;
     }
     if (EAT_BYTES(s, "Parts: ")) {
       dest->kind = PART;
@@ -237,9 +268,12 @@ static bool parse_eventdata(struct scanner *s, struct event *dest) {
   }
 
   if (EAT_BYTES(s, "<")) {
+    // DEBUG(" Ate '<'\n");
     dest->kind = TALK;
     if (!parse_nick(s, &dest->ptr1, &dest->len1)) return false;
+    // DEBUG(" Nick %u %hu\n", dest->ptr1, dest->len1);
     if (!EAT_BYTES(s, "> ")) return false;
+    // DEBUG(" Ate '> '\n");
     return parse_remaining(s, &dest->ptr2, &dest->len2);
   }
 
@@ -254,7 +288,7 @@ static bool parse_eventdata(struct scanner *s, struct event *dest) {
     dest->ptr1 = ptr1;
     dest->len1 = len1;
 
-    if (!EAT_BYTES(s, "> ")) return false;
+    if (!EAT_BYTES(s, " ")) return false;
     return parse_remaining(s, &dest->ptr2, &dest->len2);
   }
 
@@ -268,133 +302,88 @@ static bool parse_eventdata(struct scanner *s, struct event *dest) {
   return false;
 }
 
-static size_t tirclogv_parse_znc_loop(uint8_t *events_, const char *buf, size_t len) {
+static size_t tirclogv_parse_znc_loop(
+    uint8_t *events_, size_t max_events, const char *buf, size_t len
+) {
+  // offsets are stored in a uint32_t, so the buffer can't be too large
+  if ((uint32_t)len != len) return 0;
+
   assert(sizeof(struct event) == 22);
   struct event *events = (struct event*)events_;
+  struct event dummyevent;
 
   struct scanner s = (struct scanner){.buf = buf, .len = len, .cur = 0};
   size_t numev = 0;
-  while (len > 0) {
-    if (!parse_hms(&s, &events[numev])) goto parseerror;
-    if (!parse_eventdata(&s, &events[numev])) goto parseerror;
+  while (s.cur < s.len && numev < max_events) {
+    DEBUG("cur=%zu len=%zu\n", s.cur, s.len);
+    if (!parse_hms(&s, events ? &events[numev] : &dummyevent)) goto parseerror;
+    DEBUG(" hms\n");
+    if (!parse_eventdata(&s, events ? &events[numev] : &dummyevent)) goto parseerror;
+    DEBUG(" evdata cur=%zu len=%zu buf[cur]=%u\n", s.cur, s.len, (unsigned)s.buf[s.cur]);
     if (s.cur != s.len && s.buf[s.cur] != '\n') goto parseerror;
+    s.cur++;  // skip the newline
     numev++;
     continue;
 
   parseerror:
-    memset(&events[numev], 0, sizeof(struct event));
+    assert(PARSEERROR == 0);
+    if (events) memset(&events[numev], 0, sizeof(struct event));
     numev++;
     const char *p = memchr(buf + s.cur, '\n', len - s.cur);
     if (p == NULL) break;
     s.cur += (p + 1) - (buf + s.cur);
   }
 
+  DEBUG("ret numev=%zu\n", numev);
   return numev;
 }
 
-size_t tirclogv_parse_znc_numevents(const char *buf, size_t len) {
-  return tirclogv_parse_znc_loop(NULL, buf, len);
-}
-
-void tirclogv_parse_znc(uint8_t *events, const char *buf, size_t len) {
-  tirclogv_parse_znc_loop(events, buf, len);
+// Assumes there is space for evs_allocated * sizeof(struct event) items in events.
+size_t tirclogv_parse_znc(uint8_t *events, size_t evs_allocated, const char *buf, size_t len) {
+  return tirclogv_parse_znc_loop(events, evs_allocated, buf, len);
 }
 
+size_t tirclogv_count_lines(const char *buf, size_t len) {
+  size_t numln = 0;
 
-// UPBITS(3) = 0b1110'0000
-#define UPBITS(n) ((uint8_t)~((1 << (8 - n)) - 1))
-
-// If you're afraid of goto: don't worry, it's just a state machine
-static size_t tirclogv_fix_utf8_loop(char *out, const char *buf, size_t len) {
-  const char *replacement_char = "\xef\xbf\xbd";
-  const int replacement_length = 3;
-
-  size_t cur = 0, block_start = 0;
-  size_t multibyte_start = 0;  // only valid if ncont > 0
-  int ncont = 0;  // number of continuation bytes expected now
-  size_t out_cur = 0;
-
-restart:  // At this label, ncont must be 0
-  if (cur == len) return out_cur;
-  if ((uintptr_t)(buf + cur) % 16 == 0) goto vect_loop_16;
+  if (len == 0) return 0;
+  if (buf[len - 1] == '\n') len--;  // we actually count the number of '\n' below
 
-perbyte_untilalign:  // supports ncont > 0
-  {
-    size_t ntogo = 16 - (uintptr_t)(buf + cur) % 16;
-    if (len - cur < ntogo) ntogo = len - cur;
+  const int vecwidth = 16;
+  const int unrollcount = 2;
 
-    if (ntogo >= 8 && ncont == 0) {
-      if ((*(uint64_t*)(buf + cur) & 0x8080808080808080) == 0) {
-        cur += 8;
-        ntogo -= 8;
-      }
-    }
-
-    // TODO: speed up checking of multi-byte characters
-    for (size_t i = 0; i < ntogo; i++, cur++) {
-      const char c = buf[cur];
-      if ((c & UPBITS(1)) == 0) {
-        if (ncont > 0) goto incorrect_byte;
-      } else if ((c & UPBITS(2)) == UPBITS(1)) {
-        if (ncont == 0) goto incorrect_byte;
-        ncont--;
-      } else if ((c & UPBITS(3)) == UPBITS(2)) {
-        if (ncont > 0) goto incorrect_byte;
-        multibyte_start = cur;
-        ncont = 1;
-      } else if ((c & UPBITS(4)) == UPBITS(3)) {
-        if (ncont > 0) goto incorrect_byte;
-        multibyte_start = cur;
-        ncont = 2;
-      } else if ((c & UPBITS(5)) == UPBITS(4)) {
-        if (ncont > 0) goto incorrect_byte;
-        multibyte_start = cur;
-        ncont = 3;
-      } else goto incorrect_byte;
-    }
-  }
+  while (len >= vecwidth * unrollcount) {
+    const int iter_size = vecwidth * unrollcount;
+    size_t niters = len / iter_size;
+    if (niters > 256) niters = 256;  // make sure we're not overflowing the bytes
 
-  if (cur == len) {
-    if (ncont > 0) {
-      if (out) memcpy(out + out_cur, buf + block_start, multibyte_start - block_start);
-      out_cur += multibyte_start - block_start;
-      if (out) memcpy(out + out_cur, replacement_char, replacement_length);
-      out_cur += replacement_length;
-    } else {
-      if (out) memcpy(out + out_cur, buf + block_start, cur - block_start);
-      out_cur += cur - block_start;
+    assert(unrollcount == 2);
+    __m128i acc0, acc1;
+    acc0 = acc1 = _mm_set1_epi8(0);
+    for (size_t i = 0; i < niters; i++) {
+      const __m128i vec0 = _mm_loadu_si128((const __m128i*)(buf + vecwidth * (unrollcount * i + 0)));
+      const __m128i vec1 = _mm_loadu_si128((const __m128i*)(buf + vecwidth * (unrollcount * i + 1)));
+      // since cmpeq returns 0xff/0x00 for true/false, "+= (eq == 0xff)" == "-= eq"
+      // (GCC is able to see that "+= (cmpeq(...) == 0xff)" can be optimised to
+      // "-= cmpeq(...)", but then proceeds to mess things up and generates
+      // bad, quirky code anyway, so we do the optimisation manually)
+      acc0 = _mm_sub_epi8(acc0, _mm_cmpeq_epi8(vec0, _mm_set1_epi8('\n')));
+      acc1 = _mm_sub_epi8(acc1, _mm_cmpeq_epi8(vec1, _mm_set1_epi8('\n')));
     }
-    return out_cur;
-  }
+    acc0 = _mm_add_epi8(acc0, acc1);
 
-vect_loop_16:  // requires buf+cur to be 16-byte aligned
-  if (ncont > 0) goto perbyte_untilalign;
-  for (; cur + 16 <= len; cur += 16) {
-    const __m128i vec = _mm_load_si128((const __m128i*)(buf + cur));
-    // movemask takes all the top bits, which is nicely the non-ascii bytes
-    if (_mm_movemask_epi8(vec) != 0) goto perbyte_untilalign;
-  }
-  if (cur == len) return out_cur;
-  goto perbyte_untilalign;  // handle unaligned tail
+    uint8_t bytes[vecwidth];
+    memcpy(bytes, &acc0, vecwidth);
+#pragma GCC novector  // the generated vector code is rather dumb (lots of punpck{l,h})
+    for (int i = 0; i < vecwidth; i++) numln += bytes[i];
 
-incorrect_byte:  // requires buf[cur] is an incorrect byte (and thus cur < len);
-  {
-    const size_t good_until = ncont == 0 ? cur : multibyte_start;
-    if (out) memcpy(out + out_cur, buf + block_start, good_until - block_start);
-    out_cur += good_until - block_start;
+    buf += niters * iter_size;
+    len -= niters * iter_size;
   }
-  if (out) memcpy(out + out_cur, replacement_char, replacement_length);
-  out_cur += replacement_length;
-  cur += 1;
-  ncont = 0;
-  block_start = cur;
-  goto restart;
-}
 
-size_t tirclogv_fix_utf8_length(const char *buf, size_t off, size_t len) {
-  return tirclogv_fix_utf8_loop(NULL, buf + off, len);
-}
+#pragma GCC novector
+  for (size_t i = 0; i < len; i++)
+    numln += buf[i] == '\n';
 
-void tirclogv_fix_utf8(char *out, const char *buf, size_t off, size_t len) {
-  tirclogv_fix_utf8_loop(out, buf + off, len);
+  return numln;
 }