Lines Matching +full:fuzz +full:- +full:issue +full:- +full:has +full:- +full:question
6 bus][1]. In other words, it's meant to make the [bus factor][1] a non-issue.
25 and C. They both are arbitrary-precision command-line calculators with their own
30 In addition, it is also possible to build the arbitrary-precision math as a
58 This project became a passion project for me, and I continued. In mid-2019,
64 about things like fuzzing, [`scan-build`][19], [valgrind][20],
82 [According to Bryan Cantrill][10], all software has values. I think he's
150 pseudo-random number generator (for the same seed).
183 * Pseudo-Random Number Generator (see [`include/rand.h`][37]).
193 That's why `bc` has duplicated code. Remove it, and you risk `bc` not being
213 1. High-level requirements
214 2. Low-level requirements
215 3. High-level implementation
216 4. Low-level implementation
233 alias makej='make -j16'
235 alias mcmakej='make clean && make -j16'
236 alias bcdebug='CPPFLAGS="-DBC_DEBUG_CODE=1" CFLAGS="-Weverything -Wno-padded \
237 -Wno-switch-enum -Wno-format-nonliteral -Wno-cast-align \
238 -Wno-unreachable-code-return -Wno-missing-noreturn \
239 -Wno-disabled-macro-expansion -Wno-unreachable-code -Wall -Wextra \
240 -pedantic -std=c99" ./configure.sh'
241 alias bcconfig='CFLAGS="-Weverything -Wno-padded -Wno-switch-enum \
242 -Wno-format-nonliteral -Wno-cast-align -Wno-unreachable-code-return \
243 -Wno-missing-noreturn -Wno-disabled-macro-expansion -Wno-unreachable-code \
244 -Wall -Wextra -pedantic -std=c99" ./configure.sh'
245 alias bcnoassert='CPPFLAGS="-DNDEBUG" CFLAGS="-Weverything -Wno-padded \
246 -Wno-switch-enum -Wno-format-nonliteral -Wno-cast-align \
247 -Wno-unreachable-code-return -Wno-missing-noreturn \
248 -Wno-disabled-macro-expansion -Wno-unreachable-code -Wall -Wextra \
249 -pedantic -std=c99" ./configure.sh'
250 alias bcdebugnoassert='CPPFLAGS="-DNDEBUG -DBC_DEBUG_CODE=1" \
251 CFLAGS="-Weverything -Wno-padded -Wno-switch-enum -Wno-format-nonliteral \
252 -Wno-cast-align -Wno-unreachable-code-return -Wno-missing-noreturn \
253 -Wno-disabled-macro-expansion -Wno-unreachable-code -Wall -Wextra \
254 -pedantic -std=c99" ./configure.sh'
261 command-line.
279 export BC_ENV_ARGS="-l $HOME/.bcrc"
285 run `bc -s` on my `$HOME/.bcrc`.
301 t-=s
303 t-=m
305 t-=h
360 existing `.clang-format` file. More precisely, the style is whatever is output
391 * If single-line bodies are on a separate line from their headers, and the
417 Functions are documented with Doxygen-style doc comments. Functions that appear
429 This `bc` has a custom build system. The reason for this is because of
437 Turing-complete programming language. It's a terrible one, but it works.
451 1. It processes command-line arguments and figure out what the user wants to
454 3. One-by-one, it replaces placeholders (in [`Makefile.in`][70]) of the form
485 [POSIX `make`][74]-compatible `Makefile` (minus the placeholders). Here are a
604 A text file containing the text displayed for `bc -h` or `bc --help`.
606 This text just contains the command-line options and a short summary of the
612 **Warning**: The text has some `printf()` format specifiers. You need to make
617 A text file containing the text displayed for `dc -h` or `dc --help`.
619 This text just contains the command-line options and a short summary of the
625 **Warning**: The text has some `printf()` format specifiers. You need to make
648 First, all constants must be one digit. This is because otherwise, multi-digit
650 This does not happen with single-digit numbers because they are guaranteed to be
657 to set it with a single-digit number and beware the snare below...
660 from any function in the library. This is because without the `-g` option,
668 must not use *any* extensions. It has to work when users use the `-s` or `-w`
737 This file is the API for processing command-line arguments.
741 This header is the API for `bc`-only items. This includes the `bc_main()`
742 function and the `bc`-specific lexing and parsing items.
758 that it has platform-specific fixes for Windows. (If the fixes were not in this
765 This header is the API for `dc`-only items. This includes the `dc_main()`
766 function and the `dc`-specific lexing and parsing items.
783 This header is for `bc`'s implementation of command-line editing/history, which
784 is based on a [UTF-8-aware fork][28] of [`linenoise`][29].
786 For more information, see the [Command-Line History][189] section.
823 This header is the API for parsing command-line arguments.
826 to process the command-line arguments into global data *after* they have already
828 parses the command-line arguments, and [`args.h`][31] turns that parsed data
833 discovered that `getopt_long()` has different behavior on different platforms, I
834 adapted a [public-domain option parsing library][34] to do the job instead. And
862 This header defines the API for the [pseudo-random number generator
865 The PRNG only generates fixed-size integers. The magic of generating random
882 This header has several things:
885 * Compiler-specific fixes.
886 * Platform-specific fixes.
976 It has very little documentation value, other than showing what compiler options
983 This `bc` has a custom build system. The reason for this is because of
1082 collection mechanism of the [`BcNum` caching][96] works. It has been little-used
1106 #### `exec-install.sh`
1133 and run the script when I want to fuzz.
1139 This script has at least one of two major differences from most of the other
1159 ever again. So this script only has to run on the packagers machine.
1237 meant for outside use. This means that some non-POSIX utilities can be used,
1250 A script to test `bc`'s command-line expression parsing code, which, while
1269 previously-installed version of this `bc` and `dc`.
1272 `bc` using `./scripts/fuzz_prep.sh -a`, and then run it under this script. Any
1284 report mode. One-by-one, it will go through the "checklist," the list of failed
1307 alone for 32-bit.
1318 #### `safe-install.sh`
1356 Code for processing command-line arguments.
1386 There is no code in this file, but a lot of the const data has a heavy influence
1387 on code, including the order of data in arrays because that order has to
1424 The code for `bc`'s implementation of command-line editing/history, which is
1425 based on a [UTF-8-aware fork][28] of [`linenoise`][29].
1427 For more information, see the [Command-Line History][189] section.
1467 This file has no headers associated with it.
1471 The code for all of the arbitrary-precision [numbers][177] and [math][178] in
1478 The code for parsing command-line options.
1496 The code for the [pseudo-random number generator (PRNG)][179] and the special
1499 The PRNG only generates fixed-size integers. The magic of generating random
1549 The script to run the file-based error tests in `tests/<calculator>/errors/` for
1557 The script to run the line-based error tests in `tests/<calculator>/errors.txt`
1576 This script also re-runs the test three times if it fails. This is because
1629 The initial error test file for `bc`. This file has one test per line. See the
1634 The file of tests for POSIX compatibility for `bc`. This file has one test per
1676 The initial error test file for `dc`. This file has one test per line. See the
1681 The file of tests errors with the `?` command (`read()` in `bc`). This file has
1711 fuzz run. For more information, see the [Convenience][130] subsection of the
1717 fuzz run. For more information, see the [Convenience][130] subsection of the
1806 `bc` has a default `make clean` target that cleans up the build files. However,
1811 [`gen/strgen.c`][15]. It has no prerequisites.
1814 including `gen/strgen` if it was built. So this has a prerequisite on
1817 executable. It has no prerequisites.
1823 suite][124]'s [code coverage][146] capabilities. It has no prerequisites. This
1825 * `make clean_tests` cleans *everything*. It has prerequisites on all previous
1881 the Karatsuba multiplication algorithm switches to brute-force
1903 disabled, but both `BC_ENABLED` and `DC_ENABLED` must be non-zero.
1907 : This macro expands to `1` if `bc` has been built for use with Valgrind's
1914 : This macro expands to `1` if `bc` has been built for fuzzing with
1954 : If this macro expands to a non-zero integer, then `bc` is built with *a lot*
1991 make -j<cores> test
1994 Where `<cores>` is the number of cores that your computer has. Of course, this
1998 I have even tried as much as possible, to put longer-running tests near the
2024 are generated by a GNU-compatible `bc` or `dc`. See the [Generated Tests][143]
2033 and its results are generated by a GNU-compatible `bc` or `dc`. See the
2036 To add a non-generated standard test, do the following:
2182 Single-letter numbers always be set to the same value, regardless of
2225 classify them, but it's really testing multi-line numbers.
2261 : Tests the pseudo-random number generator and its special stack handling.
2265 : Tests the limits of the pseudo-random number generator `irand()`.
2292 : Tests the `is_number()` built-in function.
2296 : Tests the `is_number()` built-in function.
2304 : Tests the line-by-line behavior of `bc` with regards to `quit` in a function
2309 : Tests the line-by-line behavior of `bc` with regards to `quit`.
2313 : Tests the behavior of `bc` with a `quit` after a single-line loop.
2317 : Tests the behavior of `bc` with a `quit` after a single-line loop and a
2431 : Tests the pseudo-random number generator and its special stack handling.
2435 : Tests the `is_number()` built-in function (the `u` command).
2439 : Tests the `is_number()` built-in function (the `t` command).
2467 `-g` and `--global-stacks` flags. This means that all of the script tests for
2468 `bc` are written assuming the `-g` flag was given on the command-line
2611 : A test to ensure `dc` has the same behavior as the BSD `dc` with digi
2620 machine-generated (by [AFL++][125]) ones.
2642 are run by [`tests/errors.sh`][226]. It reads them line-by-line and shoves the
2651 command-line.
2655 Is it a simple one-liner, and you don't care if it's tested through a file?
2663 command-line, or the error requires multiple lines to reproduce, then put the
2672 The `stdin` tests specifically test the lexing and parsing of multi-line
2693 other types of tests. They usually include things like command-line parsing and
2735 use parallel execution with `make -j<cores> test_history`.
2761 Yes, the error code is not a success all the time. This is because of the UTF-8
2762 tests; `bc` gives a fatal error on any non-ASCII data because ASCII is all `bc`
2792 Instead, the tests depend on the existence of a GNU-compatible `bc` in the
2795 If [`configure.sh`][69] was run with the `-G` argument, which disables generated
2798 GNU-compatible `bc` installed.
2803 For example, `bc`'s test suite will automatically use a GNU-compatible `bc` to
2821 Adding a script has a double benefit: the script itself can be used as a test.
2827 GNU-compatible `bc` is used to generate the `<test>.txt` results file.
2836 While the test suite has a lot of targets in order to get parallel execution,
2846 In addition, there are more fine-grained targets available:
2921 The big problem the test suite has is that some `bc` code, stuff that is
2990 CC=gcc ./configure -gO3 -c
2991 make -j<cores>
2995 Note that `make coverage` does not have a `-j<cores>` part; it cannot be run in
3016 make -j<cores>
3025 make -j<cores>
3026 make -j<cores> test
3038 CFLAGS="-fsanitize=<sanitizer> ./configure -gO3 -m
3039 make -j<cores>
3040 make -j<cores> test
3045 that has zero optimization, so for `UBSan`, use the following commands:
3048 CFLAGS="-fsanitize=undefined" ./configure -gO0 -m
3049 make -j<cores>
3050 make -j<cores> test
3058 ./configure -gO3 -v
3059 make -j<cores>
3060 make -j<cores> test
3081 1. No `bash`-isms.
3083 3. Only command-line options defined in the POSIX standard for POSIX utilities
3108 ### Maintainer-Only Scripts
3156 POSIX-compatible locales are terrible.
3160 First, `gencat` does not work for generating cross-compilation. In other words,
3161 it does not generate machine-portable files. There's nothing I can do about
3204 [`scan-build`][19]. I only use it in debug mode because I have to add some
3209 function to be initialized. [`scan-build`][19] misses that fact, so I
3210 pre-initialize such locals to prevent the warnings.
3212 To run `scan-build`, do the following:
3216 scan-build make
3219 `scan-build` will print its warnings to `stdout`.
3268 at that call. Thus, every run has the exact same virtual memory setup, and each
3281 stability: the pseudo-random number generator *must* start with *exactly* the
3284 `__AFL_INIT()` call, so setting it has no runtime cost for each run, but without
3294 reasons: first, my machine has 16 cores, and second, the [AFL++][125] docs
3309 assumes the existence of `afl-clang-lto` in the `$PATH`, but if that exists, it
3310 automatically configures and builds `bc` with a fuzz-ideal build.
3312 A fuzz-ideal build has several things:
3314 * `afl-clang-lto` as the compiler. (See [AFL++ Quickstart][129].)
3316 * Full optimization (including [Link-Time Optimization][126]), for performance.
3321 There is one big thing that a fuzz-ideal build does *not* have: it does not use
3327 However, to add to [`scripts/fuzz_prep.sh`][119] making a fuzz-ideal build, in
3463 to use with varying command-line arguments, which was needed for testing `bc`'s
3464 command-line expression parsing code, and [AFL++][125] is best when testing
3471 not had to touch the command-line expression parsing code since.
3493 ./scripts/fuzz_prep.sh -a
3494 ./scripts/afl.py --asan bc1
3495 ./scripts/afl.py --asan bc2
3496 ./scripts/afl.py --asan bc3
3497 ./scripts/afl.py --asan dc
3503 These commands build an [ASan][21]-enabled build of `bc` and `dc` and then they
3505 to check that no path or crash has found any memory errors, including memory
3509 in `bc` or `dc`, [`scripts/afl.py`][94] has a timeout of 8 seconds, which is far
3528 POSIX mode is `bc`-only.
3531 These modes are designed to help users write POSIX-compatible `bc` scripts.
3535 Standard Mode is activated with the `-s` or `--standard` flags.
3542 Warning Mode is activated with the `-w` or `--warn` flags.
3544 In this mode, `bc` will issue warnings, but continue, if any constructs are used
3557 As an example, the `BcParse` struct has a pointer to the one `BcProgram` in
3566 ### [Async-Signal-Safe][115] Signal Handling
3569 `bc` is, by and large, CPU-bound. This has several consequences, but the biggest
3579 Alternatively, I/O bound programs can use the [self-pipe trick][199].
3609 Other than that, the rest of the interrupt-based implementation is best
3614 First, signal handlers can only call [async-signal-safe][115] functions.
3627 Vectors and numbers needed special consideration with the interrupt-based signal
3634 be able to interrupt a non-[async-signal-safe][115] function like `malloc()` and
3672 At first glance, it may seem like putting asserts for pointers being non-`NULL`
3716 But to store items, or to push items, or even to return items, the vector has to
3810 for general-purpose allocators to handle efficiently.
3827 slab is put into the vacated spot. This ensures that a non-special slab is
3830 ### Command-Line History
3835 It sucked, and the biggest reason why was because of the lack of command-line
3838 At first, I just dealt with it, not knowing how command-line history might be
3841 Eventually, I caved and attempted to adapt [`linenoise-mob`][28], which I had
3847 Understanding command-line history in `bc` is really about understanding VT-100
3850 Now, the history implementation of `bc` has been adapted far beyond that initial
3851 adaptation to make the command-line history implementation perfect for `bc`
3857 all of that, it does not have at least one feature: multi-line pasting from the
3899 Well, if that weren't enough, `bc` also has to handle [POSIX signals][113]. As
3915 It turns out that what I needed was a [async-signal-safe][115] form of what
3926 2. While `longjmp()` is required to be [async-signal-safe][115], if it is
3927 invoked by a signal handler that interrupted a non-[async-signal-safe][115]
3942 sig_atomic_t`. (For more information, see the [Async-Signal-Safe Signal
3944 async-signal-safe, they first need to use `BC_SIG_LOCK` to lock signals, and
3947 Code also need to do this for all global, non-atomic mutation, which means that
3950 `BC_SIG_UNLOCK` has another requirement: it must check for signals or errors and
3961 In this way, C++-style exceptions were implemented in pure C. Not fun, but it
3976 all of the buffered I/O API is basically non-[async-signal-safe][115].
3985 easily-parsable form.
3996 For this purpose, the lexer has a [vector][111] named `str` to store the data
4014 just processes command-line arguments after they are parsed by
4021 `dc`'s lexer also has to lex the register name after lexing tokens for commands
4049 [Shunting-Yard Algorithm][109] is designed to generate [Reverse Polish
4066 `dc`'s parser also has to parse the register name for commands that need
4084 |------------|-------|--------------------------------------------|
4098 | `-` | x | Subtraction |
4101 | `0-9` | x | Numbers |
4109 | `A-F` | x | Numbers |
4178 And then comes the biggest complication of all: `bc` has to assume that it is
4179 *always* at a REPL (Read-Eval-Print Loop). `bc` is, first and foremost, an
4184 All of this means that `bc` has to be able to partially parse something, store
4209 `bc`'s language is Turing-complete. That means that code needs the ability to
4228 "Cond" labels are so-called because they are used by conditionals.
4234 well-known. Cond labels are easy.
4243 "Exit" labels are so-called because they are used by code "exiting" out of `if`
4257 if the parser has no bugs. This is because every `if` statement, every loop,
4265 `bc` has expressions like you might expect in a typical programming language.
4272 That extra work is called the [Shunting-Yard algorithm][109], and the form it
4276 [Shunting-Yard algorithm][109]. Go do that before you read on.
4280 In `bc`, the [Shunting-Yard algorithm][109] is implemented with bytecode as the
4353 Since strings in `dc` are functions, and the fact that `dc` has no native loops,
4442 So `bc` has a way of encoding an index into bytecode. It does this by, after
4445 little-endian order.
4452 necessary to encode the index. It stops pushing when the index has no more bytes
4492 `dc` has no need of this extra stack, but `bc` does because arrays can be
4542 * To seed the pseudo-random number generator.
4578 In order to do arbitrary-precision math, as `bc` must do, there must be some way
4579 of representing arbitrary-precision numbers. `BcNum` in [`include/num.h`][184]
4582 (Note: the word ["limb"][214] is used below; it has a specific meaning when
4583 applied to arbitrary-precision numbers. It means one piece of the number. It can
4592 * The number of limbs the number has. This is the `len` field.
4605 between -1 and 1).
4624 scale + (BC_BASE_DIGS - 1) / BC_BASE_DIGS == rdx >> 1
4628 64-bit systems and 4 on other systems.)
4644 little-endian order. This means that the last decimal places are in the limb
4645 stored at index 0, and the most significant digits are stored at index `len-1`.
4659 * `len == 0 && scale != 0`: the number equals 0, but it has a `scale` value.
4664 equal to -1.
4665 * `(rdx >> 1) < len`: the number is greater than -1 and less than 1, not
4690 There is a question of what to do when parsing numbers and coming across digits
4695 * Use the digit as-is, multiplying it by the `ibase` to the power of the digit's
4701 It is possible to switch between the two with the `-c` and `-C` command-line
4735 ### Pseudo-Random Number Generator
4738 manpages about the pseudo-random number generator (PRNG) first; that will help
4739 you understand the guarantees it has, which is important because this section
4743 cryptographically secure PRNG available via command-line, usually
4751 On top of that, `bc` is an arbitrary-precision calculator; if I made it able to
4765 I could, of course, put the entire 255 bits into one massive arbitrary-precision
4803 3. Divide the seed by `2^128` with a `scale` of 128. (For 32-bit systems,
4807 Likewise, the algorithm to convert from a user-supplied number to a seed is:
4816 #### Generating Arbitrary-Precision Numbers
4832 Besides building `bc` in debug mode with the `-g` flag to [`configure.sh`][69],
4833 programmers can also add `-DBC_DEBUG_CODE=1` to the `CFLAGS`. This will enable
4851 First, users can probably use [profile-guided optimization][217] to optimize
4876 Also, as stated in the [build manual][219], link-time optimization is excellent
4912 statically-allocated stack (it's just a global array with a set size). Then,
4938 Even the [pseudo-random number generator][179] is included, with extra support
4951 This is because `bcl` uses thread-specific data to store the "globals" for each
4989 The encoding of errors is this: if an error happens, the value `0-error` is
4991 `0-num_errors` is an error.
5004 [5]: ./bc/A.1.md#standard-library
5006 [7]: ./bc/A.1.md#extended-library
5007 [8]: #libbc-2
5010 [11]: https://gavinhoward.com/2019/12/values-for-yao/
5011 [12]: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
5012 [13]: ./build.md#cross-compiling
5018 [19]: https://clang-analyzer.llvm.org/scan-build.html
5021 [22]: https://gavinhoward.com/2019/11/finishing-software/
5027 [28]: https://github.com/rain-1/linenoise-mob
5031 [32]: ../NEWS.md#3-0-0
5075 [76]: ##posix-shell-scripts
5078 [79]: #bc-1
5079 [80]: #dc-1
5080 [81]: ./build.md#build-type
5081 [82]: #fuzzing-1
5084 [85]: #locales-1
5085 [86]: #manuals-1
5095 [96]: #caching-of-numbers
5096 [97]: #error-handling
5108 [109]: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
5109 [110]: #bc-parsing
5113 [114]: #custom-io
5122 [123]: https://tmuxp.git-pull.com/
5123 [124]: #test-suite
5125 [126]: #link-time-optimization
5126 [127]: #fuzzing-performance
5128 [129]: #afl-quickstart
5131 [132]: https://git.gavinhoward.com/gavin/vim-bc
5137 [138]: #test-suite-portability
5140 [141]: #group-tests
5141 [142]: #build-system
5142 [143]: #generated-tests
5143 [144]: #benchmarks-1
5145 [146]: #test-coverage
5146 [147]: #integration-with-the-build-system
5147 [148]: #test-scripts
5148 [149]: #standard-tests
5149 [150]: #script-tests
5150 [151]: #error-tests
5151 [152]: #stdin-tests
5152 [153]: #read-tests
5153 [154]: #other-tests
5154 [155]: #history-tests
5156 [157]: #bcl-test
5159 [160]: #addresssanitizer-and-friends
5160 [161]: #bc-2
5161 [162]: #dc-2
5162 [163]: #alltxt-1
5166 [167]: #alltxt-3
5167 [168]: #errorstxt-1
5168 [169]: #scripts-1
5169 [170]: #scripts-2
5170 [171]: #alltxt-2
5171 [172]: #alltxt-4
5172 [173]: #async-signal-safe-signal-handling
5177 [178]: #math-style
5178 [179]: #pseudo-random-number-generator
5186 [187]: #slabs-and-slab-vectors
5187 [188]: ./build.md#extra-math
5188 [189]: #command-line-history
5190 [191]: #linux-timeconstbc-script
5193 [194]: https://www.valgrind.org/docs/manual/mc-manual.html
5196 [197]: https://clang-analyzer.llvm.org/
5197 [198]: https://unix.stackexchange.com/questions/253349/eintr-is-there-a-rationale-behind-it
5199 [200]: https://skarnet.org/cgi-bin/archive.cgi?2:mss:1607:201701:dfblejammjllfkggpcph
5200 [201]: https://slembcke.github.io/2020/10/12/CustomAllocators.html#1-slab-allocator
5213 [214]: https://gmplib.org/manual/Nomenclature-and-Types
5215 [216]: #main-and-read-functions
5216 [215]: https://www.pcg-random.org/
5217 [216]: https://lemire.me/blog/2017/08/22/testing-non-cryptographic-random-number-generators-my-resu…
5218 [217]: https://en.wikipedia.org/wiki/Profile-guided_optimization
5219 [218]: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect
5223 [222]: https://www.freebsd.org/cgi/man.cgi?query=ministat&apropos=0&sektion=0&manpath=FreeBSD+13.0-…