Restructure the top level README.md
diff --git a/README.md b/README.md
index e267197..4298468 100644
--- a/README.md
+++ b/README.md
@@ -4,45 +4,62 @@
Puffs](https://groups.google.com/d/topic/puffslang/ZX-ymyf8xh0/discussion):
Parsing Untrusted File Formats Safely).
-Wuffs is a domain-specific language and library for wrangling untrusted file
-formats safely. Wrangling includes parsing, decoding and encoding. Examples of
-such file formats include images, audio, video, fonts and compressed archives.
+Wuffs is a **memory-safe programming language** (and a **standard library**
+written in that language) for wrangling **untrusted file formats** safely.
+Wrangling includes parsing, decoding and encoding. Example file formats include
+images, audio, video, fonts and compressed archives.
-Unlike the C programming language, Wuffs is safe with respect to buffer
-overflows, integer arithmetic overflows and null pointer dereferences. The key
-difference between Wuffs and other memory-safe languages is that all such
-checks are done at compile time, not at run time. *If it compiles, it is safe*,
-with respect to those three bug classes.
+It is also **fast**. On many of its GIF decoding
+[benchmarks](/doc/benchmarks.md), Wuffs measures **2x faster than "giflib" (C),
+3x faster than "image/gif" (Go) and 7x faster than "gif" (Rust)**.
-The aim is to produce software libraries that are as safe as Go or Rust,
+
+## Goals and Non-Goals
+
+Wuffs' goal is to produce software libraries that are as safe as Go or Rust,
roughly speaking, but as fast as C, and that can be used anywhere C libraries
-are used. This includes very large C/C++ products, such as popular web browsers
+are used. This includes very large C/C++ projects, such as popular web browsers
and operating systems (using that term to include desktop and mobile user
interfaces, not just the kernel).
+[Wuffs the Library](/doc/wuffs-the-library.md) is [available](/release/c) as
+transpiled C code. Other C/C++ projects can use that library without requiring
+the [Wuffs the Language](/doc/wuffs-the-language.md) toolchain. Those projects
+can use Wuffs the Library like using any other third party C library. It's just
+not hand-written C.
+
+However, unlike hand-written C, Wuffs the Language is safe with respect to
+buffer overflows, integer arithmetic overflows and null pointer dereferences. A
+key difference between Wuffs and other memory-safe languages is that all such
+checks are done at compile time, not at run time. *If it compiles, it is safe*,
+with respect to those three bug classes.
+
The trade-off in aiming for both safety and speed is that Wuffs programs take
longer for a programmer to write, as they have to explicitly annotate their
programs with proofs of safety. A statement like `x += 1` unsurprisingly means
to increment the variable `x` by `1`. However, in Wuffs, such a statement is a
compile time error unless the compiler can also prove that `x` is not the
-maximal value of `x`'s type (e.g. `x` is not `255` if `x` is a `u8`), as the
-increment would otherwise overflow. Similarly, an integer arithmetic expression
-like `x / y` is a compile time error unless the compiler can also prove that
-`y` is not zero.
+maximal value of `x`'s type (e.g. `x` is not `255` if `x` is a `base.u8`), as
+the increment would otherwise overflow. Similarly, an integer arithmetic
+expression like `x / y` is a compile time error unless the compiler can also
+prove that `y` is not zero.
-Wuffs is not a general purpose programming language. While technically
-possible, it is unlikely that a Wuffs compiler would be worth writing in Wuffs.
+Wuffs is not a general purpose programming language. It is for writing
+libraries, especially ones that run in security-concious contexts, not
+programs. While technically possible, it is unlikely that a Wuffs compiler
+would be worth writing in Wuffs.
## What Does Wuffs Code Look Like?
-The [`std/lzw/decode_lzw.wuffs`](./std/lzw/decode_lzw.wuffs) file is a good
-example. See the "Poking Around" section below for more guidance.
+The [`/std/lzw/decode_lzw.wuffs`](/std/lzw/decode_lzw.wuffs) file is a good
+example. The [Wuffs the Language](/doc/wuffs-the-language.md) document has more
+information on how it differs from other languages in the C family.
## What Does Compile Time Checking Look Like?
-For example, making this one-line edit to the GIF codec leads to a compile time
+For example, making this one-line edit to the LZW codec leads to a compile time
error. `wuffs gen` fails to generate the C code, i.e. fails to compile
(transpile) the Wuffs code to C code:
@@ -129,204 +146,51 @@
wuffs test: some tests failed
```
-# Background
+# Directory Layout
-Decoding untrusted data, such as images downloaded from across the web, have a
-long history of security vulnerabilities. As of 2017, libpng is over 18 years
-old, and the [PNG specification is dated 2003](https://www.w3.org/TR/PNG/), but
-that well examined C library is still getting [CVE's published in
-2017](https://www.cvedetails.com/vulnerability-list/vendor_id-7294/year-2017/Libpng.html).
-
-Sandboxing and fuzzing can mitigate the danger, but they are reactions to C's
-fundamental unsafety. Newer programming languages remove entire classes of
-potential security bugs. Buffer overflows and null pointer dereferences are
-amongst the most well known.
-
-Less well known are integer overflow bugs. Offset-length pairs, defining a
-sub-section of a file, are seen in many file formats, such as OpenType fonts
-and PDF documents. A conscientious C programmer might think to check that a
-section of a file or a buffer is within bounds by writing `if (offset + length
-< end)` before processing that section, but that addition can silently
-overflow, and a maliciously crafted file might bypass the check.
-
-A variation on this theme is where `offset` is a pointer, exemplified by
-[capnproto's
-CVE-2017-7892](https://github.com/sandstorm-io/capnproto/blob/master/security-advisories/2017-04-17-0-apple-clang-elides-bounds-check.md)
-and [another
-example](https://www.blackhat.com/docs/us-14/materials/us-14-Rosenberg-Reflections-on-Trusting-TrustZone.pdf).
-For a pointer-typed offset, witnessing such a vulnerability can depend on both
-the malicious input itself and the addresses of the memory the software used to
-process that input. Those addresses can vary from run to run and from system to
-system, e.g. 32-bit versus 64-bit systems and whether dynamically allocated
-memory can have sufficiently high address values, and that variability makes it
-harder to reproduce and to catch such subtle bugs from fuzzing.
-
-In C, some integer overflow is *undefined behavior*, as per [the C99 spec
-section 3.4.3](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf). In
-Go, integer overflow is [silently
-ignored](https://golang.org/ref/spec#Integer_overflow). In Rust, integer
-overflow is [checked at run time in debug mode and silently ignored in release
-mode](http://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/)
-by default, as the run time performance penalty was deemed too great. In Swift,
-it's a [run time
-error](https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/AdvancedOperators.html#//apple_ref/doc/uid/TP40014097-CH27-ID37).
-In D, it's [configurable](http://dconf.org/2017/talks/alexandrescu.pdf). Other
-languages like Python and Haskell can automatically spill into 'big integers'
-larger than 64 bits, but this can have a performance impact when such integers
-are used in inner loops.
-
-Even if overflow is checked, it is usually checked at run time. Similarly,
-modern languages do their bounds checking at run time. An expression like
-`a[i]` is really `if ((0 <= i) && (i < a.length)) { use a[i] } else { throw }`,
-in mangled pseudo-code. Compilers for these languages can often eliminate many
-of these bounds checks, e.g. if `i` is an iterator index, but not always all of
-them.
-
-The run time cost is small, measured in nanoseconds. But if an image decoding
-library has to eat this cost per pixel, and you have a megapixel image, then
-nanoseconds become milliseconds, and milliseconds can matter.
-
-In comparison, in Wuffs, all bounds checks and arithmetic overflow checks
-happen at compile time, with zero run time overhead.
-
-
-# Getting Started
-
-Wuffs code (that is proved safe via explicit assertions) is compiled to C code
-(with those assertions removed) - it is transpiled. If you are a C/C++
-programmer and just want to *use* the C edition of the Wuffs standard library,
-then clone the repository and look at the files in the `gen/c` and `gen/h`
-directories. No other software tools are required and there are no library
-dependencies, other than C standard library concepts like `<stdint.h>`'s
-`uint32_t` type and `<string.h>`'s `memset` function.
-
-If your C/C++ project is large, you might want both the .c files (adding each
-to your build system) and the .h files. If your C/C++ project is small, you
-might only need the .c files, not the .h files, as the .c files are designed to
-be a [drop-in library](http://gpfault.net/posts/drop-in-libraries.txt.html).
-For example, if you want a GIF decoder, you only need `gif.c`. See TODO for an
-example. More complicated decoders might require multiple .c files - multiple
-modules. For example, the PNG codec (TODO) requires the deflate codec, but they
-are separate files, since HTTP can use also deflate compression (also known as
-gzip or zlib, roughly speaking) without necessarily processing PNG images.
-
-
-## Getting Deeper
-
-If you want to modify the Wuffs standard library, or compile your own Wuffs
-code, you will need to do a little more work, and will have to install at least
-the Go toolchain in order to build the Wuffs tools. To run the test suite, you
-might also have to install C compilers like clang and gcc, as well as C
-libraries (and their .h files) like libjpeg and libpng, as some tests compare
-that Wuffs produces exactly the same output as these other libraries.
-
-Running `go get -v github.com/google/wuffs/cmd/...` will download and install
-the Wuffs tools. Change `get` to `install` to re-install those programs without
-downloading, e.g. after you've modified their source code, or after a manually
-issued `git pull`. The Wuffs tools that you'll most often use are `wuffsfmt`
-(analogous to `clang-format`, `gofmt` or `rustfmt`) and `wuffs` (roughly
-analogous to `make`, `go` or `cargo`).
-
-You should now be able to run `wuffs test`. If all goes well, you should see
-some output containing the word "PASS" multiple times.
-
-
-## Poking Around
-
-Feel free to edit the `std/lzw/decode_lzw.wuffs` file, which implements the GIF
-LZW decoder. After editing, run `wuffs gen std/gif` or `wuffs test std/gif` to
-re-generate the C edition of the Wuffs standard library's GIF codec, and
-optionally run its tests.
-
-Try deleting an assert statement and re-running `wuffs gen`. The result should
-be syntactically valid, but a compile error, as some bounds checks can no
-longer be proven.
-
-Find the line `var bits u32`, which declares the bits variable and initializes
-it to zero. Try adding `bits -= 1` on a new line of code after it. Again,
-`wuffs gen` should fail, as the computation can underflow.
-
-Similarly, replacing the line `var n_bits u32` with `var n_bits u32 = 10`
-should fail, as an `n_bits < 8` assertion, a pre-condition, a few lines further
-down again cannot be proven.
-
-Similarly, changing the `4095` in `var prev_code u32[..= 4095]` either higher
-or lower should fail.
-
-Try adding `assert false` at various places, which should obviously fail, but
-should also cause `wuffs gen` to print what facts the compiler can prove at
-that point. This can be useful when debugging why Wuffs can't prove something
-you think it should be able to.
-
-
-## Running the Tests
-
-If you've changed any of the tools (i.e. changed any `.go` code), re-run `go
-install -v github.com/google/wuffs/cmd/...` and `go test
-github.com/google/wuffs/lang/...`.
-
-If you've changed any of the libraries (i.e. changed any `.wuffs` code), run
-`wuffs test` or, ideally, `wuffs test -mimic` to also check that Wuffs' output
-mimics (i.e. exactly matches) other libraries' output, such as giflib for GIF,
-libpng for PNG, etc.
-
-If your library change is an optimization, run `wuffs bench` or `wuffs bench
--mimic` both before and after your change to quantify the improvement. The
-mimic benchmark numbers should't change if you're only changing `.wuffs` code,
-but seeing zero change in those numbers is a sanity check on any unrelated
-system variance, such as software updates or virus checkers running in the
-background.
-
-
-## Directory Layout
-
-- `lang` holds the Go libraries that implement the Wuffs language: tokenizer,
+- `lang` holds the Go libraries that implement Wuffs the Language: tokenizer,
AST, parser, renderer, etc. The Wuffs tools are written in Go, but as
mentioned above, Wuffs transpiles to C code, and Go is not necessarily
involved if all you want is to use the C edition of Wuffs.
-- `lib` holds other Go libraries, not specific to the Wuffs language per se.
+- `lib` holds other Go libraries, not specific to Wuffs the Language per se.
- `internal` holds internal implementation details, as per Go's [internal
packages](https://golang.org/s/go14internal) convention.
-- `cmd` holds Wuffs' command line tools, also written in Go.
-- `std` holds the Wuffs standard library's code. The initial focus is on
- popular image codecs: BMP, GIF, JPEG, PNG, TIFF and WEBP.
-- `gen` holds the transpiled editions of that standard library. The initial
- focus is generating C code. Later on, the repository might include generated
- Go and Rust code.
-- `release` holds the releases of the Wuffs standard library.
-- `test` holds the regular tests for the Wuffs standard library.
-- `fuzz` holds the fuzz tests for the Wuffs standard library.
+- `cmd` holds Wuffs the Language' command line tools, also written in Go.
+- `std` holds Wuffs the Library's code.
+- `release` holds the releases (e.g. in their C form) of Wuffs the Library.
+- `test` holds the regular tests for Wuffs the Library.
+- `fuzz` holds the fuzz tests for Wuffs the Library.
- `script` holds miscellaneous utility programs.
- `doc` holds documentation.
-- `example` holds example programs.
-
-For a guide on how various things work together, the "99ff8e2 Let fields have
-default values" commit is an example of adding new Wuffs syntax and threading
-that all the way through to C code generation and testing.
+- `example` holds example programs for Wuffs the Library.
+- `hello-wuffs-c` holds an example program for Wuffs the Language.
# Documentation
-- [Changelog](./doc/changelog.md)
-- [Related Work](./doc/related-work.md)
-- [Roadmap](./doc/roadmap.md)
-- [Wuffs the Language](./doc/wuffs-the-language.md)
-- Wuffs the Library (TODO)
+- [Getting Started](/doc/getting-started.md). **Start here** if you want to
+ play but aren't sure how.
+- [Background](/doc/background.md).
+- [Benchmarks](/doc/benchmarks.md).
+- [Binary Size](/doc/binary-size.md).
+- [Changelog](/doc/changelog.md).
+- [Glossary](/doc/glossary.md).
+- [Related Work](/doc/related-work.md).
+- [Roadmap](/doc/roadmap.md).
+- [Wuffs the Language](/doc/wuffs-the-language.md) overview.
+- [Wuffs the Library](/doc/wuffs-the-library.md) overview and see also [API
+ categories](/doc/std).
-Measurements:
-
-- [Benchmarks](./doc/benchmarks.md)
-- [Binary Size](./doc/binary-size.md)
+The [Note](/doc/note) directory also contains various short articles.
# Status
-Proof of concept. Version 0.1 at best. API and ABI aren't stabilized yet. There
-are plenty of tests to create, docs to write and TODOs to do. The compiler
-undoubtedly has bugs. Assertion checking needs more rigor, especially around
-side effects and aliasing, and being sufficiently well specified to allow
-alternative implementations. Lots of detail needs work, but the broad
-brushstrokes are there.
+Version 0.2. The API and ABI aren't stabilized yet. The compiler undoubtedly
+has bugs. Assertion checking needs more rigor, especially around side effects
+and aliasing, and being sufficiently well specified to allow alternative
+implementations. Lots of detail needs work, but the broad brushstrokes are
+there.
# Discussion
@@ -337,7 +201,7 @@
# Contributing
-The [CONTRIBUTING.md](./CONTRIBUTING.md) file contains instructions on how to
+The [CONTRIBUTING.md](/CONTRIBUTING.md) file contains instructions on how to
file the Contributor License Agreement before sending any pull requests (PRs).
Of course, if you're new to the project, it's usually best to discuss any
proposals and reach consensus before sending your first PR.
@@ -356,4 +220,4 @@
---
-Updated on October 2019.
+Updated on December 2019.
diff --git a/doc/README.md b/doc/README.md
index 476ae1d..7ced100 100644
--- a/doc/README.md
+++ b/doc/README.md
@@ -4,4 +4,5 @@
- A [standard library](/doc/wuffs-the-library.md) written in that programming
language.
-The [top level README](/README.md) also has some general remarks.
+"[Getting Started](/doc/getting-started.md)" has some suggestions if you're
+new. The [top level README](/README.md) also has some general remarks.
diff --git a/doc/background.md b/doc/background.md
new file mode 100644
index 0000000..133c2bf
--- /dev/null
+++ b/doc/background.md
@@ -0,0 +1,59 @@
+# Background
+
+Decoding untrusted data, such as images downloaded from across the web, have a
+long history of security vulnerabilities. As of 2019, libpng is over 20 years
+old, and the [PNG specification is dated 2003](https://www.w3.org/TR/PNG/), but
+that well examined C library is still getting [CVE's published in
+2019](https://www.cvedetails.com/vulnerability-list/vendor_id-7294/year-2019/Libpng.html).
+
+Sandboxing and fuzzing can mitigate the danger, but they are reactions to C's
+fundamental unsafety. Newer programming languages remove entire classes of
+potential security bugs. Buffer overflows and null pointer dereferences are
+amongst the most well known.
+
+Less well known are integer overflow bugs. Offset-length pairs, defining a
+sub-section of a file, are seen in many file formats, such as OpenType fonts
+and PDF documents. A conscientious C programmer might think to check that a
+section of a file or a buffer is within bounds by writing `if (offset + length
+< end)` before processing that section, but that addition can silently
+overflow, and a maliciously crafted file might bypass the check.
+
+A variation on this theme is where `offset` is a pointer, exemplified by
+[capnproto's
+CVE-2017-7892](https://github.com/sandstorm-io/capnproto/blob/master/security-advisories/2017-04-17-0-apple-clang-elides-bounds-check.md)
+and [another
+example](https://www.blackhat.com/docs/us-14/materials/us-14-Rosenberg-Reflections-on-Trusting-TrustZone.pdf).
+For a pointer-typed offset, witnessing such a vulnerability can depend on both
+the malicious input itself and the addresses of the memory the software used to
+process that input. Those addresses can vary from run to run and from system to
+system, e.g. 32-bit versus 64-bit systems and whether dynamically allocated
+memory can have sufficiently high address values, and that variability makes it
+harder to reproduce and to catch such subtle bugs from fuzzing.
+
+In C, some integer overflow is *undefined behavior*, as per [the C99 spec
+section 3.4.3](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf). In
+Go, integer overflow is [silently
+ignored](https://golang.org/ref/spec#Integer_overflow). In Rust, integer
+overflow is [checked at run time in debug mode and silently ignored in release
+mode](http://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/)
+by default, as the run time performance penalty was deemed too great. In Swift,
+it's a [run time
+error](https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/AdvancedOperators.html#//apple_ref/doc/uid/TP40014097-CH27-ID37).
+In D, it's [configurable](http://dconf.org/2017/talks/alexandrescu.pdf). Other
+languages like Python and Haskell can automatically spill into 'big integers'
+larger than 64 bits, but this can have a performance impact when such integers
+are used in inner loops.
+
+Even if overflow is checked, it is usually checked at run time. Similarly,
+modern languages do their bounds checking at run time. An expression like
+`a[i]` is really `if ((0 <= i) && (i < a.length)) { use a[i] } else { throw }`,
+in mangled pseudo-code. Compilers for these languages can often eliminate many
+of these bounds checks, e.g. if `i` is an iterator index, but not always all of
+them.
+
+The run time cost is small, measured in nanoseconds. But if an image decoding
+library has to eat this cost per pixel, and you have a megapixel image, then
+nanoseconds become milliseconds, and milliseconds can matter.
+
+In comparison, in Wuffs, all bounds checks and arithmetic overflow checks
+happen at compile time, with zero run time overhead.
diff --git a/doc/getting-started.md b/doc/getting-started.md
new file mode 100644
index 0000000..857cf06
--- /dev/null
+++ b/doc/getting-started.md
@@ -0,0 +1,77 @@
+# Getting Started
+
+If you're looking to **write your own Wuffs code** outside of its standard
+library, e.g. you want to safely decode your own custom file format, see the
+[Wuffs the Language](/doc/wuffs-the-language.md) document and the
+[/hello-wuffs-c](/hello-wuffs-c) example instead of this document.
+
+If you're looking to just **use the Wuffs standard library**, e.g. you want to
+safely decode some gzip'ed data in your C program, see the [Wuffs the
+Library](/doc/wuffs-the-library.md) document and the [other examples](/example)
+instead of this document.
+
+If you're looking to **modify the Wuffs language**, it's probably best to ask
+the [mailing list](https://groups.google.com/forum/#!forum/wuffs).
+
+If you're looking to **modify the Wuffs standard library**, keep reading.
+
+---
+
+First, install the Go toolchain in order to build the Wuffs tools. To run the
+test suite, you might also have to install C compilers like clang and gcc, as
+well as C libraries (and their .h files) like libjpeg and libpng, as some tests
+compare that Wuffs produces exactly the same output as these other libraries.
+
+Running `go get -v github.com/google/wuffs/cmd/...` will download and install
+the Wuffs tools. Change `get` to `install` to re-install those programs without
+downloading, e.g. after you've modified their source code, or after a manually
+issued `git pull`. The Wuffs tools that you'll most often use are `wuffsfmt`
+(analogous to `clang-format`, `gofmt` or `rustfmt`) and `wuffs` (roughly
+analogous to `make`, `go` or `cargo`).
+
+You should now be able to run `wuffs test`. If all goes well, you should see
+some output containing the word "PASS" multiple times.
+
+
+## Poking Around
+
+Feel free to edit the `std/lzw/decode_lzw.wuffs` file, which implements the GIF
+LZW decoder. After editing, run `wuffs gen std/gif` or `wuffs test std/gif` to
+re-generate the C edition of the Wuffs standard library's GIF codec, and
+optionally run its tests.
+
+Try deleting an assert statement and re-running `wuffs gen`. The result should
+be syntactically valid, but a compile error, as some bounds checks can no
+longer be proven.
+
+Find the `var bits : base.u32` line, which declares the bits variable,
+implicitly initialized to zero. Try adding `bits -= 1` on a new line of code
+after all of the `var` lines. Again, `wuffs gen` should fail, as the
+computation can underflow.
+
+Similarly, changing the `4095` in `var prev_code : base.u32[..= 4095]` either
+higher or lower should fail.
+
+Try adding `assert false` at various places, which should obviously fail, but
+should also cause `wuffs gen` to print what facts the compiler knows at that
+point. This can be useful when debugging why Wuffs can't prove something you
+think it should be able to.
+
+
+## Running the Tests
+
+If you've changed any of the tools (i.e. changed any `.go` code), re-run `go
+install -v github.com/google/wuffs/cmd/...` and `go test
+github.com/google/wuffs/lang/...`.
+
+If you've changed any of the libraries (i.e. changed any `.wuffs` code), run
+`wuffs test` or, ideally, `wuffs test -mimic` to also check that Wuffs' output
+mimics (i.e. exactly matches) other libraries' output, such as giflib for GIF,
+libpng for PNG, etc.
+
+If your library change is an optimization, run `wuffs bench` or `wuffs bench
+-mimic` both before and after your change to quantify the improvement. The
+mimic benchmark numbers should't change if you're only changing `.wuffs` code,
+but seeing zero change in those numbers is a sanity check on any unrelated
+system variance, such as software updates or virus checkers running in the
+background.
diff --git a/doc/wuffs-the-library.md b/doc/wuffs-the-library.md
index 67d98c8..b1b0514 100644
--- a/doc/wuffs-the-library.md
+++ b/doc/wuffs-the-library.md
@@ -16,7 +16,7 @@
depending on Wuffs the Language tools (such as its compiler). Although the
standard library's source code is in Wuffs the Language, the transpiled form is
also checked into the repository. Using the standard library's C form would be
-like using any other third party C library. It's just not hand written C.
+like using any other third party C library. It's just not hand-written C.
To do so, you need to download only one file, from the
[`/release/c`](/release/c) directory. Wuffs the Library' C form ships as a
