path: root/linux/util.c

#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include <stdio.h>

#define STATE_SKIP_OVERLONG ((size_t)-1)
#define STATE_SKIP_NEXT_LF ((size_t)-2)
#define MAX_SCRATCH_SIZE (PTRDIFF_MAX >> 1)
#define MIN_SCRATCH_SIZE 2

static inline bool starts_line_end(char ch) {
  return ch == '\r' || ch == '\n';
}

static inline int line_end_seq_len(const char *s, size_t lim) {
  if (lim < 1) return -1;
  switch (s[0]) {
    case '\n':
      return 1;
    case '\r':
      if (lim == 1) return -1;
      return s[1] == '\n' ? 2 : 1;
  }
  return 0; /* not a line ending sequence */
}

static inline bool is_whitespace(char ch) {
  return ch >= 0 && ch < ' ';
}

/* this function will split lines in buf (which should have *pbufstrlen characters). This function handles partial
 * lines by saving partials into the provided scratch buffer (which is expected to be scratchsz bytes long). The pointer
 * returned in cmdline will be NULL or a pointer to a NUL-terminated string which is the complete line (with beginning/ending
 * whitespace stripped, including line endings).
 *
 * For the purposes of this function, a "line ending" (or "line-ending sequence") is a single LF, single CR, or a CR followed
 * by a LF. Each line-ending sequence in buf will ultimately be returned as a line by this function. A CRLF sequence which is
 * split across reads will not result in two lines being returned, since they were a part of the same line-ending sequence.
 *
 * NOTE: buf and scratch must not overlap (nor must any other pointer arguments to this function).
 * NOTE: buf will be mutated by this function (if for no other reason than to memmove() consumed characters away)
 * NOTE: overlong lines will be handled with specific return values to this function. Do NOT attempt to grow scratch (e.g., with realloc)
 *       in response to an overlong line. If an overlong line is reported, that line will be skipped, and resizing the
 *       scratch buffer between calls to this function is not a supported usage at this time.
 * NOTE: this function is able to handle NUL bytes in buf, but since *cmdline is NUL-terminated rather than a length-string,
 *       the portion of the line following the first NUL byte cannot be observed by the caller. Those characters still contribute
 *       to the length limit, though.
 *
 * Arguments:
 * (inout)          char *restrict buf: a buffer with *pbufstrlen characters. These will be processed and possibly consumed by the function.
 * (inout)      char *restrict scratch: contains private data for the function ("scratch" data). Do not modify this manually between calls.
 *                                      This array does not need to be initialized to any specific value on first call, but it's good practice
 *                                      to memset() it to 0.
 * (inout) size_t *restrict priv_state: contains private state information for the function. Initialize *priv_state to 0 before the first
 *                                      call to this function.
 * (inout) size_t *restrict pbufstrlen: the string-length of *buf ("strlen" as in the number of actual characters of buf to be processed).
 *                                      Pass in however many bytes a call like read(2) returned. The function will "consume" characters from
 *                                      buf, move the remaining bytes in buf to the front, and return the new string length of buf in this
 *                                      variable (so you can immediately call the function again to consume more lines of text).
 * (   in)            size_t scratchsz: the size of the scratch buffer. Note that this value must be at least MIN_SCRATCH_SIZE (2) and
 *                                      no more than MAX_SCRATCH_SIZE (PTRDIFF_MAX >> 1). This value fixes the max line length, which
 *                                      is equal to scratchsz - 1 (to leave room for a NUL-terminating byte).
 * (  out)     char **restrict cmdline: the returned pointer to the line. This pointer points into one of the buffers passed into the function and
 *                                      therefore need not be freed.
 *
 * Returns:
 *  0 (success): the function executed successfully. check *cmdline for the line (or NULL) and *pbufstrlen to see if more data is needed.
 *  1 (overlong): an overlong line was detected (now might be a good time to inform the user of this).
 *  2 (continue): an overlong line from a previous call is being drained from buf.
 * -1 (invalid): the usage of the function was invalid. The state of out or inout pointer variables has not changed.
 *               Note that invalid usage of the function is not guaranteed to cause this value to be returned. */
static int split_line(char *restrict buf, char *restrict scratch, size_t *restrict pscrstrlen, size_t *restrict pbufstrlen, size_t scratchsz, char **restrict cmdline) {
  /* expected behavior: each "newline sequence" (\n, \r\n, or \r (followed by a character other than \n)) is considered a "line".
   * whitespace is stripped from the start and end of a line. */
  const char *line = buf;
  size_t linelen = *pbufstrlen;
  const char *eol;

  /* make sure the max line length is within bounds */
  if (scratchsz > MAX_SCRATCH_SIZE) {
    scratchsz = MAX_SCRATCH_SIZE;
  }

  if (scratchsz < MIN_SCRATCH_SIZE) {
    return -1;
  }

  if (linelen < 1) {
    return -1; /* it's invalid usage to provide this function with no new data */
  }

  if (*pscrstrlen == STATE_SKIP_NEXT_LF) { /* skip next LF if present, otherwise begin reading next line */
    /* last invocation found us in the situation where we had a CR. skip the following LF if present, since it
     * would still be a part of the same line-ending sequence. */
    if (line[0] == '\n') {
      ++line;
      --linelen;
      *pscrstrlen = 0; /* we definitely have no scratch saved since the line just ended. */
    }
  } else if (*pscrstrlen == STATE_SKIP_OVERLONG) { /* skip whatever remains of the previous line which was too long */
    for (size_t idx = 0; idx < linelen; ++idx) {
      if (starts_line_end(line[idx])) {
        /* line ending (CR or LF) found */
        int seqlen = line_end_seq_len(line + idx, linelen - idx);
        if (seqlen < 0) {
          /* CR found at the end of the input. need to read more */
          *pscrstrlen = STATE_SKIP_NEXT_LF;
          *cmdline = NULL;
          *pbufstrlen = 0; /* consumed entire buffer */
          return 2;
        } else {
          line += seqlen;
          linelen -= seqlen;
          goto overlong_skipped;
        }
      }
    }

    /* overlong line not finished yet... */
    *pbufstrlen = 0; /* consumed entire buffer (all a part of this line) */
    *cmdline = NULL;
    return 2;

overlong_skipped:
    *pscrstrlen = 0; /* clear "skip overlong" state */

    if (linelen == 0) {
      /* buffer contained only the remainder of the line */
      *cmdline = NULL;
      return 0;
    }
  }

  assert(linelen > 0);

  if (*pscrstrlen == 0) {
    /* skip initial whitespace before line */
    for (size_t idx = 0; idx < linelen; ++idx) {
      if (!is_whitespace(line[idx])) {
        line += idx;
        linelen -= idx;
        goto found_sol;
      }

      if (starts_line_end(line[idx])) {
        line += idx;
        linelen -= idx;
        eol = line;
        goto found_eol;
      }
    }

    /* buf is all whitespace */
    *pbufstrlen = 0; /* consume entire buffer */
    *cmdline = NULL;
    return 0;

found_sol:
    ;
  }

  /* start of line found already (either begins in scratch or start of buf) */
  for (size_t idx = 0; idx < linelen; ++idx) {
    if (starts_line_end(line[idx])) {
      eol = line + idx;
      goto found_eol;
    }
  }

  /* eol not found */
  if (*pscrstrlen + linelen >= scratchsz) {
    /* overfull line (cannot fit into scratch) */
    *pscrstrlen = STATE_SKIP_OVERLONG;
    *pbufstrlen = 0;
    *cmdline = NULL;
    return 1;
  }

  memcpy(scratch + *pscrstrlen, line, linelen);
  *pscrstrlen += linelen;
  *pbufstrlen = 0;
  *cmdline = NULL;
  return 0;

found_eol: /* set eol before coming here */
  ;

  /* length of last chunk of the line */
  size_t lineendlen = eol - line;

  /* length of line-ending sequence */
  int eollen = line_end_seq_len(eol, linelen - lineendlen);
  int real_eollen = eollen < 0 ? 1 : eollen;

  /* start of the next line (might be just outside of buf) */
  const char *sonl = eol + real_eollen;

  /* must save scratch length here because it will be modified later */
  size_t oldscratchlen = *pscrstrlen;
  size_t newscratchlen = oldscratchlen + lineendlen;

  /* value to be returned */
  int ret;

  if (eollen < 0) {
    *pscrstrlen = STATE_SKIP_NEXT_LF;
  } else {
    *pscrstrlen = 0;
  }

  *pbufstrlen -= sonl - buf;

  if (newscratchlen >= scratchsz) {
    /* line too long */
    *cmdline = NULL;
    ret = 1;
  } else {
    memcpy(scratch + oldscratchlen, line, lineendlen);

    /* search backwards for the real non-whitespace end of the string */
    for (size_t idx = newscratchlen; idx > 0; --idx) {
      if (!is_whitespace(scratch[idx - 1])) {
        scratch[idx] = '\0';
        goto found_real_eol;
      }
    }

    scratch[0] = '\0'; /* string is all whitespace I guess */

found_real_eol:
    *cmdline = scratch;
    ret = 0;
  }

  memmove(buf, sonl, *pbufstrlen);
  return ret;
}

int test_main(void) {
  char scratch[17];
  size_t state = 0;
  size_t bufstrlen;
  char buf[16];
  char *cmdline;

  scratch[16] = (char)0xfe;
  strcpy(buf, "amogus\nline2\n");
  bufstrlen = strlen(buf);
  assert(split_line(buf, scratch, &state, &bufstrlen, 16, &cmdline) == 0);
  printf("%016zx %s\n", state, cmdline);
  assert(scratch[16] == (char)0xfe);
  assert(state == 0);
  assert(bufstrlen == 6);
  assert(!strcmp(cmdline, "amogus"));

  assert(split_line(buf, scratch, &state, &bufstrlen, 16, &cmdline) == 0);
  printf("%016zx %s\n", state, cmdline);
  assert(scratch[16] == (char)0xfe);
  assert(state == 0);
  assert(bufstrlen == 0);
  assert(!strcmp(cmdline, "line2"));
  return 0;
}