Lines Matching +full:turing +full:- +full:complete
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],
150 pseudo-random number generator (for the same seed).
183 * Pseudo-Random Number Generator (see [`include/rand.h`][37]).
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
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
570 The file to generate the benchmark to benchmark the Newton-Raphson division in
575 The file to generate the benchmark to benchmark the Newton-Raphson division in
580 The file to generate the benchmark to benchmark the Newton-Raphson square root
585 The file to generate the benchmark to benchmark the Newton-Raphson square root
624 A text file containing the text displayed for `bc -h` or `bc --help`.
626 This text just contains the command-line options and a short summary of the
637 A text file containing the text displayed for `dc -h` or `dc --help`.
639 This text just contains the command-line options and a short summary of the
668 First, all constants must be one digit. This is because otherwise, multi-digit
670 This does not happen with single-digit numbers because they are guaranteed to be
677 to set it with a single-digit number and beware the snare below...
680 from any function in the library. This is because without the `-g` option,
688 must not use *any* extensions. It has to work when users use the `-s` or `-w`
757 This file is the API for processing command-line arguments.
761 This header is the API for `bc`-only items. This includes the `bc_main()`
762 function and the `bc`-specific lexing and parsing items.
778 that it has platform-specific fixes for Windows. (If the fixes were not in this
785 This header is the API for `dc`-only items. This includes the `dc_main()`
786 function and the `dc`-specific lexing and parsing items.
803 This header is for `bc`'s implementation of command-line editing/history, which
804 is based on a [UTF-8-aware fork][28] of [`linenoise`][29].
806 For more information, see the [Command-Line History][189] section.
843 This header is the API for parsing command-line arguments.
846 to process the command-line arguments into global data *after* they have already
848 parses the command-line arguments, and [`args.h`][31] turns that parsed data
854 adapted a [public-domain option parsing library][34] to do the job instead. And
882 This header defines the API for the [pseudo-random number generator
885 The PRNG only generates fixed-size integers. The magic of generating random
905 * Compiler-specific fixes.
906 * Platform-specific fixes.
1102 collection mechanism of the [`BcNum` caching][96] works. It has been little-used
1126 #### `exec-install.sh`
1257 meant for outside use. This means that some non-POSIX utilities can be used,
1270 A script to test `bc`'s command-line expression parsing code, which, while
1289 previously-installed version of this `bc` and `dc`.
1292 `bc` using `./scripts/fuzz_prep.sh -a`, and then run it under this script. Any
1304 report mode. One-by-one, it will go through the "checklist," the list of failed
1327 alone for 32-bit.
1338 #### `safe-install.sh`
1376 Code for processing command-line arguments.
1444 The code for `bc`'s implementation of command-line editing/history, which is
1445 based on a [UTF-8-aware fork][28] of [`linenoise`][29].
1447 For more information, see the [Command-Line History][189] section.
1491 The code for all of the arbitrary-precision [numbers][177] and [math][178] in
1498 The code for parsing command-line options.
1516 The code for the [pseudo-random number generator (PRNG)][179] and the special
1519 The PRNG only generates fixed-size integers. The magic of generating random
1569 The script to run the file-based error tests in `tests/<calculator>/errors/` for
1577 The script to run the line-based error tests in `tests/<calculator>/errors.txt`
1596 This script also re-runs the test three times if it fails. This is because
1901 the Karatsuba multiplication algorithm switches to brute-force
1923 disabled, but both `BC_ENABLED` and `DC_ENABLED` must be non-zero.
1974 : If this macro expands to a non-zero integer, then `bc` is built with *a lot*
2011 make -j<cores> test
2018 I have even tried as much as possible, to put longer-running tests near the
2044 are generated by a GNU-compatible `bc` or `dc`. See the [Generated Tests][143]
2053 and its results are generated by a GNU-compatible `bc` or `dc`. See the
2056 To add a non-generated standard test, do the following:
2202 Single-letter numbers always be set to the same value, regardless of
2245 classify them, but it's really testing multi-line numbers.
2281 : Tests the pseudo-random number generator and its special stack handling.
2285 : Tests the limits of the pseudo-random number generator `irand()`.
2312 : Tests the `is_number()` built-in function.
2316 : Tests the `is_number()` built-in function.
2324 : Tests the line-by-line behavior of `bc` with regards to `quit` in a function
2329 : Tests the line-by-line behavior of `bc` with regards to `quit`.
2333 : Tests the behavior of `bc` with a `quit` after a single-line loop.
2337 : Tests the behavior of `bc` with a `quit` after a single-line loop and a
2451 : Tests the pseudo-random number generator and its special stack handling.
2455 : Tests the `is_number()` built-in function (the `u` command).
2459 : Tests the `is_number()` built-in function (the `t` command).
2487 `-g` and `--global-stacks` flags. This means that all of the script tests for
2488 `bc` are written assuming the `-g` flag was given on the command-line
2644 machine-generated (by [AFL++][125]) ones.
2666 are run by [`tests/errors.sh`][226]. It reads them line-by-line and shoves the
2675 command-line.
2679 Is it a simple one-liner, and you don't care if it's tested through a file?
2687 command-line, or the error requires multiple lines to reproduce, then put the
2696 The `stdin` tests specifically test the lexing and parsing of multi-line
2717 other types of tests. They usually include things like command-line parsing and
2759 use parallel execution with `make -j<cores> test_history`.
2785 Yes, the error code is not a success all the time. This is because of the UTF-8
2786 tests; `bc` gives a fatal error on any non-ASCII data because ASCII is all `bc`
2816 Instead, the tests depend on the existence of a GNU-compatible `bc` in the
2819 If [`configure.sh`][69] was run with the `-G` argument, which disables generated
2822 GNU-compatible `bc` installed.
2827 For example, `bc`'s test suite will automatically use a GNU-compatible `bc` to
2851 GNU-compatible `bc` is used to generate the `<test>.txt` results file.
2870 In addition, there are more fine-grained targets available:
3014 CC=gcc ./configure -gO3 -c
3015 make -j<cores>
3019 Note that `make coverage` does not have a `-j<cores>` part; it cannot be run in
3040 make -j<cores>
3049 make -j<cores>
3050 make -j<cores> test
3062 CFLAGS="-fsanitize=<sanitizer> ./configure -gO3 -m
3063 make -j<cores>
3064 make -j<cores> test
3072 CFLAGS="-fsanitize=undefined" ./configure -gO0 -m
3073 make -j<cores>
3074 make -j<cores> test
3082 ./configure -gO3 -v
3083 make -j<cores>
3084 make -j<cores> test
3105 1. No `bash`-isms.
3107 3. Only command-line options defined in the POSIX standard for POSIX utilities
3132 ### Maintainer-Only Scripts
3180 POSIX-compatible locales are terrible.
3184 First, `gencat` does not work for generating cross-compilation. In other words,
3185 it does not generate machine-portable files. There's nothing I can do about
3228 [`scan-build`][19]. I only use it in debug mode because I have to add some
3233 function to be initialized. [`scan-build`][19] misses that fact, so I
3234 pre-initialize such locals to prevent the warnings.
3236 To run `scan-build`, do the following:
3240 scan-build make
3243 `scan-build` will print its warnings to `stdout`.
3305 stability: the pseudo-random number generator *must* start with *exactly* the
3333 assumes the existence of `afl-clang-lto` in the `$PATH`, but if that exists, it
3334 automatically configures and builds `bc` with a fuzz-ideal build.
3336 A fuzz-ideal build has several things:
3338 * `afl-clang-lto` as the compiler. (See [AFL++ Quickstart][129].)
3340 * Full optimization (including [Link-Time Optimization][126]), for performance.
3345 There is one big thing that a fuzz-ideal build does *not* have: it does not use
3351 However, to add to [`scripts/fuzz_prep.sh`][119] making a fuzz-ideal build, in
3487 to use with varying command-line arguments, which was needed for testing `bc`'s
3488 command-line expression parsing code, and [AFL++][125] is best when testing
3495 not had to touch the command-line expression parsing code since.
3517 ./scripts/fuzz_prep.sh -a
3518 ./scripts/afl.py --asan bc1
3519 ./scripts/afl.py --asan bc2
3520 ./scripts/afl.py --asan bc3
3521 ./scripts/afl.py --asan dc
3527 These commands build an [ASan][21]-enabled build of `bc` and `dc` and then they
3552 POSIX mode is `bc`-only.
3555 These modes are designed to help users write POSIX-compatible `bc` scripts.
3559 Standard Mode is activated with the `-s` or `--standard` flags.
3566 Warning Mode is activated with the `-w` or `--warn` flags.
3590 ### [Async-Signal-Safe][115] Signal Handling
3593 `bc` is, by and large, CPU-bound. This has several consequences, but the biggest
3603 Alternatively, I/O bound programs can use the [self-pipe trick][199].
3633 Other than that, the rest of the interrupt-based implementation is best
3638 First, signal handlers can only call [async-signal-safe][115] functions.
3651 Vectors and numbers needed special consideration with the interrupt-based signal
3658 be able to interrupt a non-[async-signal-safe][115] function like `malloc()` and
3696 At first glance, it may seem like putting asserts for pointers being non-`NULL`
3834 for general-purpose allocators to handle efficiently.
3851 slab is put into the vacated spot. This ensures that a non-special slab is
3854 ### Command-Line History
3859 It sucked, and the biggest reason why was because of the lack of command-line
3862 At first, I just dealt with it, not knowing how command-line history might be
3865 Eventually, I caved and attempted to adapt [`linenoise-mob`][28], which I had
3871 Understanding command-line history in `bc` is really about understanding VT-100
3875 adaptation to make the command-line history implementation perfect for `bc`
3881 all of that, it does not have at least one feature: multi-line pasting from the
3939 It turns out that what I needed was a [async-signal-safe][115] form of what
3950 2. While `longjmp()` is required to be [async-signal-safe][115], if it is
3951 invoked by a signal handler that interrupted a non-[async-signal-safe][115]
3966 sig_atomic_t`. (For more information, see the [Async-Signal-Safe Signal
3968 async-signal-safe, they first need to use `BC_SIG_LOCK` to lock signals, and
3971 Code also need to do this for all global, non-atomic mutation, which means that
3985 In this way, C++-style exceptions were implemented in pure C. Not fun, but it
4000 all of the buffered I/O API is basically non-[async-signal-safe][115].
4009 easily-parsable form.
4038 just processes command-line arguments after they are parsed by
4073 [Shunting-Yard Algorithm][109] is designed to generate [Reverse Polish
4108 |------------|-------|--------------------------------------------|
4122 | `-` | x | Subtraction |
4125 | `0-9` | x | Numbers |
4133 | `A-F` | x | Numbers |
4203 *always* at a REPL (Read-Eval-Print Loop). `bc` is, first and foremost, an
4233 `bc`'s language is Turing-complete. That means that code needs the ability to
4252 "Cond" labels are so-called because they are used by conditionals.
4258 well-known. Cond labels are easy.
4267 "Exit" labels are so-called because they are used by code "exiting" out of `if`
4296 That extra work is called the [Shunting-Yard algorithm][109], and the form it
4300 [Shunting-Yard algorithm][109]. Go do that before you read on.
4304 In `bc`, the [Shunting-Yard algorithm][109] is implemented with bytecode as the
4469 little-endian order.
4566 * To seed the pseudo-random number generator.
4602 In order to do arbitrary-precision math, as `bc` must do, there must be some way
4603 of representing arbitrary-precision numbers. `BcNum` in [`include/num.h`][184]
4607 applied to arbitrary-precision numbers. It means one piece of the number. It can
4629 between -1 and 1).
4648 scale + (BC_BASE_DIGS - 1) / BC_BASE_DIGS == rdx >> 1
4652 64-bit systems and 4 on other systems.)
4668 little-endian order. This means that the last decimal places are in the limb
4669 stored at index 0, and the most significant digits are stored at index `len-1`.
4688 equal to -1.
4689 * `(rdx >> 1) < len`: the number is greater than -1 and less than 1, not
4719 * Use the digit as-is, multiplying it by the `ibase` to the power of the digit's
4725 It is possible to switch between the two with the `-c` and `-C` command-line
4759 ### Pseudo-Random Number Generator
4762 manpages about the pseudo-random number generator (PRNG) first; that will help
4767 cryptographically secure PRNG available via command-line, usually
4775 On top of that, `bc` is an arbitrary-precision calculator; if I made it able to
4789 I could, of course, put the entire 255 bits into one massive arbitrary-precision
4827 3. Divide the seed by `2^128` with a `scale` of 128. (For 32-bit systems,
4831 Likewise, the algorithm to convert from a user-supplied number to a seed is:
4840 #### Generating Arbitrary-Precision Numbers
4856 Besides building `bc` in debug mode with the `-g` flag to [`configure.sh`][69],
4857 programmers can also add `-DBC_DEBUG_CODE=1` to the `CFLAGS`. This will enable
4875 First, users can probably use [profile-guided optimization][217] to optimize
4900 Also, as stated in the [build manual][219], link-time optimization is excellent
4936 statically-allocated stack (it's just a global array with a set size). Then,
4962 Even the [pseudo-random number generator][179] is included, with extra support
4975 This is because `bcl` uses thread-specific data to store the "globals" for each
5013 The encoding of errors is this: if an error happens, the value `0-error` is
5015 `0-num_errors` is an error.
5028 [5]: ./bc/A.1.md#standard-library
5030 [7]: ./bc/A.1.md#extended-library
5031 [8]: #libbc-2
5034 [11]: https://gavinhoward.com/2019/12/values-for-yao/
5035 [12]: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
5036 [13]: ./build.md#cross-compiling
5042 [19]: https://clang-analyzer.llvm.org/scan-build.html
5045 [22]: https://gavinhoward.com/2019/11/finishing-software/
5051 [28]: https://github.com/rain-1/linenoise-mob
5055 [32]: ../NEWS.md#3-0-0
5099 [76]: ##posix-shell-scripts
5102 [79]: #bc-1
5103 [80]: #dc-1
5104 [81]: ./build.md#build-type
5105 [82]: #fuzzing-1
5108 [85]: #locales-1
5109 [86]: #manuals-1
5119 [96]: #caching-of-numbers
5120 [97]: #error-handling
5132 [109]: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
5133 [110]: #bc-parsing
5137 [114]: #custom-io
5146 [123]: https://tmuxp.git-pull.com/
5147 [124]: #test-suite
5149 [126]: #link-time-optimization
5150 [127]: #fuzzing-performance
5152 [129]: #afl-quickstart
5155 [132]: https://git.gavinhoward.com/gavin/vim-bc
5161 [138]: #test-suite-portability
5164 [141]: #group-tests
5165 [142]: #build-system
5166 [143]: #generated-tests
5167 [144]: #benchmarks-1
5169 [146]: #test-coverage
5170 [147]: #integration-with-the-build-system
5171 [148]: #test-scripts
5172 [149]: #standard-tests
5173 [150]: #script-tests
5174 [151]: #error-tests
5175 [152]: #stdin-tests
5176 [153]: #read-tests
5177 [154]: #other-tests
5178 [155]: #history-tests
5180 [157]: #bcl-test
5183 [160]: #addresssanitizer-and-friends
5184 [161]: #bc-2
5185 [162]: #dc-2
5186 [163]: #alltxt-1
5190 [167]: #alltxt-3
5191 [168]: #errorstxt-1
5192 [169]: #scripts-1
5193 [170]: #scripts-2
5194 [171]: #alltxt-2
5195 [172]: #alltxt-4
5196 [173]: #async-signal-safe-signal-handling
5201 [178]: #math-style
5202 [179]: #pseudo-random-number-generator
5210 [187]: #slabs-and-slab-vectors
5211 [188]: ./build.md#extra-math
5212 [189]: #command-line-history
5214 [191]: #linux-timeconstbc-script
5217 [194]: https://www.valgrind.org/docs/manual/mc-manual.html
5220 [197]: https://clang-analyzer.llvm.org/
5221 [198]: https://unix.stackexchange.com/questions/253349/eintr-is-there-a-rationale-behind-it
5223 [200]: https://skarnet.org/cgi-bin/archive.cgi?2:mss:1607:201701:dfblejammjllfkggpcph
5224 [201]: https://slembcke.github.io/2020/10/12/CustomAllocators.html#1-slab-allocator
5237 [214]: https://gmplib.org/manual/Nomenclature-and-Types
5239 [216]: #main-and-read-functions
5240 [215]: https://www.pcg-random.org/
5241 [216]: https://lemire.me/blog/2017/08/22/testing-non-cryptographic-random-number-generators-my-resu…
5242 [217]: https://en.wikipedia.org/wiki/Profile-guided_optimization
5243 [218]: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect
5247 [222]: https://www.freebsd.org/cgi/man.cgi?query=ministat&apropos=0&sektion=0&manpath=FreeBSD+13.0-…