swar

# SWAR

Byte-set guards for Elixir that classify seven bytes at a time, in pure BEAM
code. No NIFs, no CPU feature checks.

SWAR means SIMD Within A Register: several bytes are packed into one integer and
tested with arithmetic. `SWAR.defbyteset/2` lets you describe the accepted bytes
once, then generates matching byte, word and tail-padding helpers.

```elixir
defmodule Scan do
  require SWAR

  SWAR.defbyteset(:unescaped, [0x20..0x7E, not ?", not ?\\])

  @word SWAR.word_bytes()

  def count(bin), do: count(bin, 0)

  defp count(<<w::size(@word)-unit(8), rest::binary>>, n) when is_unescaped_word(w),
    do: count(rest, n + @word)

  for size <- (@word - 1)..1//-1 do
    defp count(<<w::size(unquote(size))-unit(8)>>, n)
         when is_unescaped_word(unescaped_pad(w, unquote(size))),
         do: n + unquote(size)
  end

  defp count(<<byte, rest::binary>>, n) when is_unescaped(byte),
    do: count(rest, n + 1)

  defp count(_rest, n), do: n
end
```

## What gets generated

For `SWAR.defbyteset(:unescaped, spec)`, the default helpers are:

| helper | kind | use |
| --- | --- | --- |
| `is_unescaped(byte)` | guard | test one byte |
| `is_unescaped_word(word)` | guard | test a `word_bytes()`-byte word |
| `unescaped_pad(word, size)` | macro | pad a short tail before testing it as a word |

All generated helpers are private to the module that calls `defbyteset/2`.

More helpers are available with `define:`:

| helper | use |
| --- | --- |
| `unescaped_mask(word)` | returns `0x80` in accepted lanes and `0` elsewhere |
| `unescaped_leading(word)` | counts accepted bytes from the start of the word |
| `unescaped_trailing(word)` | counts accepted bytes from the end of the word |
| `unescaped_count(word)` | counts accepted bytes anywhere in the word |

```elixir
SWAR.defbyteset(:digit, ?0..?9, define: :all)
SWAR.defbyteset(:plain, [not ?", not ?\\], define: [:byte, :word, :leading])
```

Use `_leading/1` after a word guard fails when you need the accepted prefix
length:

```elixir
defp scan(<<w::size(@word)-unit(8), rest::binary>>, n) when is_plain_word(w),
  do: scan(rest, n + @word)

defp scan(<<w::size(@word)-unit(8), _rest::binary>>, n),
  do: n + plain_leading(w)

defp scan(tail, n), do: byte_scan(tail, n)
```

The byte guard, word guard, pad macro and mask macro can be used in guards.
`_leading/1`, `_trailing/1` and `_count/1` expand to blocks, so use them in
function bodies.

## Specs

A spec is one term or a list of terms. Supported terms are:

* literal bytes: `?a`, `0x2E`
* literal ranges: `?a..?z`, `0x20..0x7E`
* charlists: `~c"-:"`, `[?+, ?/]`
* negated terms: `not ?"`, `not(?p..?r)`; `!` also works

Positive terms are unioned. Negated terms are subtracted from that union, or
from all ASCII bytes when the spec contains only negations.

```elixir
SWAR.defbyteset(:base64, [?A..?Z, ?a..?z, ?0..?9, ~c"+/"])
SWAR.defbyteset(:printable, [0x20..0x7E, not ?", not ?\\])
SWAR.defbyteset(:no_cr, [not ?\r])
```

The generated code uses a normalized set: ranges are sorted, merged and made
disjoint before expansion. These two specs generate the same checks:

```elixir
[0x20..0x7E, not ?", not ?#, not ?\\]
[0x20..0x21, 0x24..0x5B, 0x5D..0x7E]
```

Bytes must be literal values in `0..0x7F`. Other values raise `ArgumentError`
while the macro expands.

## Bytes above `0x7F`

By default, specs describe ASCII only. That is what you want for alphabets such
as base64 or decimal digits.

Use `high: true` when every byte above `0x7F` should also be accepted. This is
useful for delimiter scans over arbitrary text, such as reading until a quote or
backslash, where non-ASCII bytes are just more non-delimiters.

```elixir
SWAR.defbyteset(:plain, [not ?", not ?\\],
  high: true,
  define: [:byte, :word, :leading]
)
```

`high: true` does not decode UTF-8. It only says high bytes belong to the set.

## Reading digits

`SWAR.uint(word, size)` reads `size` ASCII digits, most significant first, from a
word. Validate the word first with a digit byteset.

```elixir
SWAR.defbyteset(:digit, ?0..?9, define: [:byte, :word, :pad])

defp to_integer(<<w::size(7)-unit(8), rest::binary>>, acc) when is_digit_word(w),
  do: to_integer(rest, acc * 10_000_000 + SWAR.uint(w, 7))

defp to_integer(<<byte, rest::binary>>, acc) when is_digit(byte),
  do: to_integer(rest, acc * 10 + (byte - ?0))
```

This pays off for longer runs of digits. For short fixed fields such as dates,
ordinary byte guards are usually simpler and at least as fast.

## When it helps

SWAR is best when:

* the accepted set is a few ranges, not many scattered bytes
* the input usually has runs of at least seven accepted bytes
* the scan works mostly on ASCII, or `high: true` is correct for the problem
* the input is long enough that call overhead is not the main cost

It is usually not worth it when:

* the set has more than about eight or nine range terms
* the scan usually stops in the first few bytes
* accepted runs are shorter than a word
* high bytes need to be decoded rather than skipped

The benchmarks in `bench/` cover delimiter scans, `String.printable?/2`-style
checks, digit parsing, manual single-byte/range comparisons and sets with
different numbers of range terms.

To see the direct comparison against ordinary byte-at-a-time code, run:

```sh
mix run bench/manual.exs
```

This benchmark uses Benchee and reports iterations per second plus relative
speed for each set shape and input.

Representative results from Linux, AMD Ryzen 7 7840HS, Elixir 1.20.0, Erlang
29.0, with JIT enabled (`manual / SWAR`; values are average ns per call):

| input | single `?a` | `not ?!` | one range | three ranges |
| --- | ---: | ---: | ---: | ---: |
| 1 byte, accepted | 30.7 / 60.2 | 30.0 / 49.1 | 30.8 / 52.8 | 31.0 / 53.8 |
| 7 bytes, accepted | 43.5 / 31.0 | 40.8 / 31.9 | 42.0 / 33.2 | 43.4 / 33.6 |
| 1 KB, accepted | 1,700 / 390 | 1,740 / 550 | 1,750 / 490 | 2,180 / 740 |
| 1 KB, reject first | 51.4 / 80.1 | 59.1 / 57.8 | 63.2 / 46.8 | 56.0 / 67.6 |
| 1 KB, reject last | 1,730 / 400 | 1,880 / 570 | 1,920 / 500 | 2,200 / 750 |

The exact numbers vary by machine, but the pattern is the useful result: a
manual check is preferable for tiny inputs and usually for an early rejection.
Once the input contains accepted runs of seven or more bytes, SWAR generally
wins; on accepted 1 KB inputs it was 3.0–4.4× faster here. Multiple ranges add
work to the SWAR word guard, but still beat the three manual range comparisons
on long accepted input.

The short-input crossover is especially clear for mixed-case hex:

| accepted input | lowercase hex<br>manual / SWAR ns | mixed-case hex<br>manual / SWAR ns |
| --- | ---: | ---: |
| 1 byte | 29.8 / 49.4 | 30.5 / 48.6 |
| 2 bytes | 31.0 / 51.5 | 33.2 / 63.3 |
| 3 bytes | 32.7 / 66.1 | 33.5 / 65.6 |
| 4 bytes | 35.2 / 54.2 | 36.3 / 48.6 |
| 5 bytes | 38.0 / 56.4 | 40.2 / 67.1 |
| 6 bytes | 39.3 / 44.4 | 38.9 / 51.9 |
| 7 bytes | 42.7 / 32.0 | 43.8 / 32.9 |
| 8 bytes | 46.3 / 37.9 | 44.3 / 41.5 |
| 16 bytes | 69.7 / 43.5 | 72.9 / 48.9 |
| 32 bytes | 98.2 / 52.3 | 107.0 / 55.6 |
| 1 KB | 2,070 / 590 | 2,180 / 740 |

For a focused run, use `BENCH_CASE=hex BENCH_INPUT=accepted mix run
bench/manual.exs`. The full script also includes rejection-at-first/last cases.

It compares a single-character set (`byte == ?a`), a negated character
(`byte != ?!`), one contiguous range (`?a <= byte <= ?z`), lowercase hex
(`0..9`, `a..f`), mixed-case hex (`0..9`, `a..f`, `A..F`) and three ranges
(`0..9`, `A..Z`, `a..z`) over short and long binaries, with accepted input and a
rejection at either end. Expect the manual version to win for very short input
or an early rejection: SWAR has to load and classify a seven-byte word before
it can help. SWAR starts to make sense when accepted runs are several words
long, especially when the set has multiple ranges that would make the manual
byte guard more expensive. Use these numbers as guidance on your machine;
benchmark the actual input distribution before choosing it.

As a quick rule of thumb:

| workload | likely choice |
| --- | --- |
| One byte or a short fixed field | Manual comparison or ordinary guards |
| One character/range over a long accepted binary | SWAR can pay; measure it |
| Lowercase or mixed-case hex over long input | SWAR is a good candidate |
| Several ranges over long input | SWAR often pays, but the advantage shrinks as ranges multiply |
| Early rejection or fragmented/short runs | Manual guards are often simpler and faster |

## Debug output

Use `debug: true` to print the generated code at compile time:

```elixir
SWAR.defbyteset(:printable, [?\a..?\r, ?\e, 0x20..0x7F], debug: true)
```

The printed code is self-contained, so it can be pasted into a project if you
want the generated guard without depending on this package. It also includes a
rough performance estimate based on the number of range terms.

## Why seven bytes

Seven bytes fit in 56 bits, which stays inside a BEAM small integer on 64-bit
systems. An eight-byte word would overflow into a heap-allocated bignum during
the arithmetic and lose the optimization.

## Tests

```sh
mix test
```

The test suite checks generated guards against independently written byte sets,
random words, high-bit cases, padding, optional helpers, error paths, Elixir
core guard parity, debug output and `SWAR.uint/2`.

## License

Licensed under the Apache License, Version 2.0. See [`LICENSE`](LICENSE) for the
full license text.