C parsing work

1 files changed, 400 insertions, 0 deletions

diff --git a/cbits/znc.c b/cbits/znc.c
new file mode 100644
index 0000000..5bac7fd
--- /dev/null
+++ b/cbits/znc.c
@@ -0,0 +1,400 @@
+#include <stddef.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <ctype.h>
+#include <string.h>
+#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).
+
+
+struct scanner {
+  const char *buf;
+  size_t len;
+  size_t cur;  // cursor
+};
+
+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,
+};
+
+#pragma pack(1)
+struct event {
+  uint8_t H, M, S;
+  uint8_t kind;  // event_kind
+  uint32_t ptr1, ptr2, ptr3;
+  uint16_t len1, len2, len3;
+};
+
+// 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];
+  const size_t len = s->len - s->cur;
+  if (len < 11) return false;
+  if (loc[0] != '[' || loc[3] != ':' || loc[6] != ':' || loc[9] != ']' || loc[10] != ' ')  return false;
+  if (!isdigit(loc[1]) || !isdigit(loc[2]) ||
+      !isdigit(loc[4]) || !isdigit(loc[5]) ||
+      !isdigit(loc[7]) || !isdigit(loc[8]))
+     return false;
+
+  dest->H = 10 * (loc[1] - '0') + loc[2] - '0';
+  dest->M = 10 * (loc[4] - '0') + loc[5] - '0';
+  dest->S = 10 * (loc[7] - '0') + loc[8] - '0';
+  s->cur += 11;
+  return true;
+}
+
+static inline bool eat_bytes(struct scanner *s, const char *tok, size_t toklen) {
+  const char *const loc = &s->buf[s->cur];
+  const size_t len = s->len - s->cur;
+  if (len >= toklen && memcmp(loc, tok, toklen) == 0) {
+    s->cur += toklen;
+    return true;
+  }
+  return false;
+}
+
+#define EAT_BYTES(scanner_, tok_) eat_bytes(scanner_, tok_, strlen(tok_))
+
+static bool parse_nick(struct scanner *s, uint32_t *destptr, uint16_t *destlen) {
+  // Delimiter bytes:
+  // \t \n \v \r SP <  >
+  // 09 0a 0b 0d 20 3c 3e
+  //
+  // None of the delimiter bytes have the bit 0x40 set, and the majority of
+  // IRC nicks consist entirely of bytes with 0x40 set (which include
+  // a-zA-Z[]_`). "Guest12" style nicks do have a numeric suffix, but since the
+  // fallback loop is at the end, most of it is done with the fast check anyway.
+
+  const char *const buf = s->buf;
+  const size_t len = s->len;
+  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] != '\t' && buf[cur] != '\n' && buf[cur] != '\v' && buf[cur] != '\r' &&
+      buf[cur] != ' ' && buf[cur] != '<' && buf[cur] != '>')
+    cur++;
+
+  if (cur == startcur) return false;
+  *destptr = startcur;
+  *destlen = cur - startcur;
+  s->cur = cur;
+  return true;
+}
+
+static bool parse_inside_parens(struct scanner *s, uint32_t *destptr, uint16_t *destlen) {
+  const char *const buf = s->buf;
+  const size_t len = s->len;
+  size_t cur = s->cur;
+
+  if (cur + 2 >= 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));
+    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;
+  }
+
+tail_loop:
+  while (cur < len) {
+    if (buf[cur] == ')') goto close_found;
+    if (buf[cur] == '\n') return false;
+    cur++;
+  }
+
+close_found:
+  *destptr = startcur;
+  *destlen = cur - startcur;
+  s->cur = cur + 1;  // skip the closing paren
+  return true;
+}
+
+static bool parse_enclose_tail(
+    struct scanner *s, uint32_t *destptr, uint16_t *destlen, char leftdelim, char rightdelim
+) {
+  const char *const buf = s->buf;
+  const size_t len = s->len;
+  size_t cur = s->cur;
+
+  if (cur + 2 >= 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 (cur == startcur) return false;
+  const size_t rightdelim_cur = cur - 1;
+  if (buf[rightdelim_cur] != rightdelim) return false;
+
+  *destptr = startcur;
+  *destlen = rightdelim_cur - startcur;
+  s->cur = cur;  // skip the rightdelim, point to the newline
+  return true;
+}
+
+static bool parse_remaining(struct scanner *s, uint32_t *destptr, uint16_t *destlen) {
+  const char *const buf = s->buf;
+  const size_t len = s->len;
+  size_t cur = s->cur;
+
+  if (cur >= len) return false;
+
+  const size_t startcur = cur;
+  const char *p = memchr(buf + cur, '\n', len - cur);
+  if (p == NULL) return false;
+  cur = p - (buf + cur);
+
+  *destptr = startcur;
+  *destlen = cur - startcur;
+  s->cur = cur;
+  return true;
+}
+
+// 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;
+  if (!EAT_BYTES(s, " ")) return false;
+  if (!parse_inside_parens(s, &dest->ptr2, &dest->len2)) return false;
+  if (withtail)
+    if (!parse_enclose_tail(s, &dest->ptr3, &dest->len3, '(', ')')) return false;
+  return true;
+}
+
+static bool parse_eventdata(struct scanner *s, struct event *dest) {
+  if (EAT_BYTES(s, "*** ")) {
+    if (EAT_BYTES(s, "Joins: ")) {
+      dest->kind = JOIN;
+      return parse_useract(s, dest, false);
+    }
+    if (EAT_BYTES(s, "Parts: ")) {
+      dest->kind = PART;
+      return parse_useract(s, dest, true);
+    }
+    if (EAT_BYTES(s, "Quits: ")) {
+      dest->kind = QUIT;
+      return parse_useract(s, dest, true);
+    }
+
+    if (!parse_nick(s, &dest->ptr1, &dest->len1)) return false;
+    if (EAT_BYTES(s, " is now known as ")) {
+      dest->kind = RENICK;
+      return parse_nick(s, &dest->ptr2, &dest->len2);
+    }
+    if (EAT_BYTES(s, " sets mode: ")) {
+      dest->kind = MODE;
+      return parse_remaining(s, &dest->ptr2, &dest->len2);
+    }
+    if (EAT_BYTES(s, " was kicked by ")) {
+      dest->kind = KICK;
+      if (!parse_nick(s, &dest->ptr2, &dest->len2)) return false;
+      if (!EAT_BYTES(s, " ")) return false;
+      return parse_enclose_tail(s, &dest->ptr3, &dest->len3, '(', ')');
+    }
+    if (EAT_BYTES(s, " changes topic to ")) {
+      dest->kind = TOPIC;
+      return parse_enclose_tail(s, &dest->ptr2, &dest->len2, '\'', '\'');
+    }
+
+    return false;
+  }
+
+  if (EAT_BYTES(s, "<")) {
+    dest->kind = TALK;
+    if (!parse_nick(s, &dest->ptr1, &dest->len1)) return false;
+    if (!EAT_BYTES(s, "> ")) return false;
+    return parse_remaining(s, &dest->ptr2, &dest->len2);
+  }
+
+  if (EAT_BYTES(s, "-")) {
+    dest->kind = NOTICE;
+    uint32_t ptr1;
+    uint16_t len1;
+    if (!parse_nick(s, &ptr1, &len1)) return false;
+
+    if (len1 > 0 && s->buf[ptr1 + len1 - 1] == '-') len1--;
+    if (len1 == 0) return false;
+    dest->ptr1 = ptr1;
+    dest->len1 = len1;
+
+    if (!EAT_BYTES(s, "> ")) return false;
+    return parse_remaining(s, &dest->ptr2, &dest->len2);
+  }
+
+  if (EAT_BYTES(s, "* ")) {
+    dest->kind = ACT;
+    if (!parse_nick(s, &dest->ptr1, &dest->len1)) return false;
+    if (!EAT_BYTES(s, " ")) return false;
+    return parse_remaining(s, &dest->ptr2, &dest->len2);
+  }
+
+  return false;
+}
+
+static size_t tirclogv_parse_znc_loop(uint8_t *events_, const char *buf, size_t len) {
+  assert(sizeof(struct event) == 22);
+  struct event *events = (struct event*)events_;
+
+  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;
+    if (s.cur != s.len && s.buf[s.cur] != '\n') goto parseerror;
+    numev++;
+    continue;
+
+  parseerror:
+    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);
+  }
+
+  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);
+}
+
+
+// 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;
+
+perbyte_untilalign:  // supports ncont > 0
+  {
+    size_t ntogo = 16 - (uintptr_t)(buf + cur) % 16;
+    if (len - cur < ntogo) ntogo = len - cur;
+
+    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;
+    }
+  }
+
+  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;
+    }
+    return out_cur;
+  }
+
+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
+
+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;
+  }
+  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);
+}
+
+void tirclogv_fix_utf8(char *out, const char *buf, size_t off, size_t len) {
+  tirclogv_fix_utf8_loop(out, buf + off, len);
+}