Category: Programming

  • The Mojibake library runs on Kandelo

    The Mojibake library runs its +4,500,000 unit tests on Linux, macOS, FreeBSD, OpenBSD, NetBSD, Haiku, Windows 11, and, of course, WASM. So it’s time to add support for Kandelo.

    Kandelo is a POSIX-compatible multi-process kernel for WebAssembly that runs command-line tools, server stacks, and early graphical demos in the browser or Node.js with syscall-level compatibility.

    So it has everything I need; Mojikake tests use a small subset of C functions.

    Setup and first test

    I already have Nix, so nothing to do except ./run.sh setup and wait for end. So the only thing to do is move the Mojibake amalgamation and the “Hello World” code to run it.

    mojibake.h
    mojibake.c
    mojibake-example.c

    I then wrote a small script in examples/mojibake/build.sh that run wasm32posix-cc.

    zaerl@zaerl kandelo % scripts/dev-shell.sh bash examples/build-mojibake.sh
    kandelo dev shell — LLVM 21.1.7, Rust (pinned via rust-toolchain.toml), Node 24, Erlang 28 (minimal), SDK on PATH
    kandelo dev shell — LLVM 21.1.7, Rust (pinned via rust-toolchain.toml), Node 24, Erlang 28 (minimal), SDK on PATH
    Compiling mojibake-example...
    Built /Users/.../kandelo/examples/mojibake-example.wasm
    Running mojibake-example...
    [worker] user program lacks a kandelo.abi.contract stamp — legacy binary predates the ABI-contract-digest rollout. Rebuild it through the local-build engine to pick up the check. See docs/abi-versioning.md.
    Cafe<CC><81>
    Caf<C3><A9>
    "文字化け" encoded in UTF-8 is 12 bytes long, and 4 codepoints long
    Straße -> strasse

    And it works! And uname(2) reports wasm-posix 1.0.0 wasm32 .

    Now it’s time for the test suite.

    The test suite

    Mojibake uses all 20 test files and loads them using an fopen(). But it’s easy to get them without copying them. So next:

    1. Set MJB_TEST_SOURCE_DIR to the local Mojibake repository folder
    2. Run wasm32posix-cc on all C files
    3. And run it
    zaerl@zaerl kandelo % scripts/dev-shell.sh bash -c 'MJB_SOURCE_DIR=/Users/zaerl/Desktop/work/personal/mojibake bash examples/mojibake/build.sh'
    kandelo dev shell — LLVM 21.1.7, Rust (pinned via rust-toolchain.toml), Node 24, Erlang 28 (minimal), SDK on PATH
    kandelo dev shell — LLVM 21.1.7, Rust (pinned via rust-toolchain.toml), Node 24, Erlang 28 (minimal), SDK on PATH
    Compiling mojibake-test (38 sources)...
    Built /Users/.../kandelo/examples/mojibake/mojibake-test.wasm
    Running mojibake-test in /Users/.../mojibake...
    [worker] user program lacks a kandelo.abi.contract stamp — legacy binary predates the ABI-contract-digest rollout. Rebuild it through the local-build engine to pick up the check. See docs/abi-versioning.md.
    Running tests with no filter
    Test: bidi_class
    Test: bidi
    Test: break_line
    Test: break_sentence
    Test: break_word
    Test: case
    Test: caseless
    Test: cjk
    Test: codepoint
    Test: collation
    Test: east_asian_width
    Test: embedded_null
    Test: emoji
    Test: encoding
    Test: example
    Test: filter
    Test: format
    Test: hangul_composition
    Test: hangul
    Test: identifier
    Test: idna
    Test: locales
    Test: mojibake
    Test: next
    Test: normalization
    Test: plane
    Test: properties
    Test: quick_check
    Test: security
    Test: segmentation
    Test: special_case
    Test: string
    Test: terminal_width
    Test: utf
    Test: version
    Test cases valid/run: 35/35
    Tests valid/run: 4561431/4561431
    Execution time: 3.8230 seconds

    It works without any changes! And the performance is very close to the core time (~1.8s). This inspired me to open a PR: https://github.com/zaerl/mojibake/pull/98.

    Until next time.

  • Updating Mojibake to Unicode 18.0.0

    I’ve updated Mojibake to Unicode 18. The beta period is over, and I don’t think there’s any need to wait for the latest summer fixes. My library generates all the files automatically, so I’m confident the generator script will not crash in September.

    New emojis, like the U+1FADD (PICKLE), a meteor, and others, you say. But those are not a problem until you add something. When you change something is the problem. But fortunately, the Unicode standard is pretty backward compatible.

    Step 1: analysis

    The news can be found in the draft document at https://www.unicode.org/versions/Unicode18.0.0/ with my initial thoughts.

    1. Unicode 18.0 adds 13,047 characters, for a total of 172,848 characters: not a problem. The library’s size will increase slightly.
    2. Four new scripts: it’s ok; enums are automatically generated
    3. JurchenSources.txt, SealSources.txt: not used right now. Will check later. See https://www.unicode.org/reports/tr60/tr60-2.html#Modifications
    4. Other UTS have been updated accordingly: not a problem once the tests are ok.
    5. Errata: it’s ok
    6. Stability Policy Update: ok
    7. New blocks: automatically generated
    8. Conformance Changes: CONFORMANCE_REQUIREMENTS.md is already ok, just some tweaks at C4

    Now it’s the time of UAXs, the most important in my opinion. I had only a couple of “let’s hope for the best” moments:

    1. Rule LB12a was changed to disallow a break between BA and GL: pretty dangerous
    2. Rule GB9c (“Do not break within certain combinations with Indic_Conjunct_Break (InCB)=Linker.”) has been revised: same

    When you change a rule, it isn’t always a good idea.

    Step 2: generating new data tables

    I changed UNICODE_VERSION to draft on the generate script and tried to run make generate.

    utils/generate/tables/case.ts:164
    throw new Error(`Simple case folding mapping is too large to pack: ${row.codepoint}`);

    Not a good start. What happened? It happened that Mojibake is trying to save as much data as possible, and it was too much of an optimization. Unicode added to the CaseFolding.txt.

    1DF95; F; 0073 0073; # LATIN SMALL LIGATURE LONG S WITH DESCENDER S
    1DF95; S; 00DF; # LATIN SMALL LIGATURE LONG S WITH DESCENDER S

    What does this mean? That the U+1DF95, a character outside BMP, has been added to the special cases.

    BMP is Plane 0; it is the Basic Multilingual Plane, AKA the first 16 bits that were used in the UCS2 encoding before we discovered that we had more than 65,535 characters.

    How the old packing worked

    Simple mappings were stored as one uint32_t:

    bits 31........16 | bits 15.........0
    source codepoint | mapped codepoint

    The generator did:

    (row.codepoint << 16) | row.mapping

    For example, the mapping U+1E9E -> U+00DF was packed as:

    0x1E9E00DF
    ^^^^ source U+1E9E
    ^^^^ target U+00DF

    One mapping occupies four bytes. However, each side only has 16 bits, so both values must be no greater than U+FFFF.

    Why did U+1DF95 not fit?

    Simple: U+1DF95 > U+FFFF. Packing it into the old format would require: 0x1DF95 << 16

    That needs 37 bits before adding the mapping. A 32-bit value would silently lose the leading 1, decoding the source as U+DF95 instead of U+1DF95.

    The old generator deliberately protected against this corruption:

    if(row.codepoint > 0xFFFF || row.mapping > 0xFFFF) {
    throw new Error(...);
    }

    Always be redundant in throwing errors!

    The new supplementary format

    A Unicode codepoint needs at most 21 bits. Therefore, the new supplementary entry uses two 21-bit fields inside a uint64_t:

    bits 41........21 | bits 20.........0
    source codepoint | mapped codepoint

    The generator packs it with: (BigInt(row.codepoint) << 21n) | BigInt(row.mapping)

    And generates a new C table with such a long name I choose to remember myself that Unicode is a convoluted standard:

    static const uint64_t mjb_unicode_case_fold_simple_supplementary_mappings[] = {
    0x03BF2A000DFULL,
    };

    We have two tables now. I didn’t want to have only one; otherwise, I would have double the size. The new one has only one entry. Don’t be alone you, new codepoint from around the block (pun); I’m pretty sure you will have new friends in the near future.

    Step 3: try the tests

    The generation worked well. Time to test things. On the first run, I got 122,773 failures. [insert here a very sad emoji here]

    So it’s time to apply the changes.

    LB12a

    [^SP BA HY HH] × GL is now [^SP HY HH] × GL. This was scaring me, but it was a one-line change.

    U+1DF95

    The infamous new codepoint needed to be added to the mjb_maybe_has_special_casing function together with the other eight.

    GB9c

    Finally, some simplifications here.

    \p{InCB=Consonant} [ \p{InCB=Extend} \p{InCB=Linker} ]
    * \p{InCB=Linker} [ \p{InCB=Extend} \p{InCB=Linker} ]*
    × \p{InCB=Consonant}
    become
    \p{InCB=Linker} \p{InCB=Extend}* × \p{InCB=Consonant}

    It has greatly simplified the code.

    Jurchen and Seal were added to the table for computing implicit weights

    I was wrong here; I thought it would have been automatic. Check the draft document to see the changes at https://www.unicode.org/reports/tr10/tr10-54.html#Reserved_Weights.

    Before Unicode 18, I had a implicit_ranges static arrays, but now it’s not enough. Too boring as an argument to be part of a blog post. Check the PR for details if you are interested.

    Step 4: final cleanup

    The cleanup didn’t clean anything at all. All the URLs to a https://www.unicode.org/* needed to be updated, and it created a lot of noise.

    Total number of tests passed from 1,610,123 to 1,600,176, so it lost 10k tests? But it makes sense:

    DatasetUnicode 17 rowsUnicode 18 rowsChange
    CollationTest_NON_IGNORABLE.txt208,070212,267+4,197
    CollationTest_SHIFTED.txt229,860212,267−17,593
    Combined collation−13,396
    Other tests+3,449
    Final difference−9,947

    1,610,123 −9,947 = 1,600,176

    Step 5: no other steps

    Unicode is not the actual standard, I know. Should I have been waiting? Nah. It was fun, and pretty exciting.

    Until next time.

  • Being on Hacker News after years of work

    Last night, I had the courage to publish the Mojibake C library I’ve worked on for years on Hacker News. https://news.ycombinator.com/item?id=48941123

    +15 comments and +15 stars on GitHub after one day? Wow, such a great achievement, you might say. After years of work, a number with two letters?

    Well, it is a great one for me.

    I don’t care to be the most popular Unicode library out there; I don’t. If even a single person uses it, it will be the best for me.

    Open source is one of the most important aspects of my life. I remember I discovered it when I saw that very long GNU General Public License version 2 LICENSE file attached to a software I was using on Linux. I don’t remember exactly which one, probably Emacs, but too many years have passed.

    It didn’t make a lot of sense to me the “free” term that was used. But then later I got it when I started using bbPress for the Italian forums.

    We don’t make software for free, we make it for freedom

    That’s the motto we use at my company (Automattic). And that’s the difference between free candy and free software. Writing software is fun, interesting, and constructive, and it’s always a source of knowledge you’ll carry with you forever.

    Until next time.

  • Prefix compression of thousands of similar strings

    In the Mojibake library I use the data of the Unicode standard UnicodeData.txt file. That file is automatically generated and full of similar strings.

    00E7;LATIN SMALL LETTER C WITH CEDILLA;...
    00E8;LATIN SMALL LETTER E WITH GRAVE;Ll;...
    00E9;LATIN SMALL LETTER E WITH ACUTE;Ll;...
    00EA;LATIN SMALL LETTER E WITH CIRCUMFLEX;...
    00EB;LATIN SMALL LETTER E WITH DIAERESIS;...
    00EC;LATIN SMALL LETTER I WITH GRAVE;...
    ...

    The aim of Mojibake is to be as small as possible, and the name column of the unicode_data table is by far the largest piece of data in my SQLite database. How to make the database as small as possible? Techniques are multiple.

    Remove automatically generated entries

    The UnicodeData.txt file contains generated names, especially for old or unused characters. Example: the entire block from U+13000 to U+143FF is made of sequential names:

    13000;EGYPTIAN HIEROGLYPH A001;Lo;0;L;;;;;N;;;;;
    13001;EGYPTIAN HIEROGLYPH A002;Lo;0;L;;;;;N;;;;;
    13002;EGYPTIAN HIEROGLYPH A003;Lo;0;L;;;;;N;;;;;
    13003;EGYPTIAN HIEROGLYPH A004;Lo;0;L;;;;;N;;;;;

    As well of ANATOLIAN HIEROGLYPH, CUNEIFORM SIGN, CJK Compatibility Ideographs, Etc. Everything can be removed or simply rebuilt at runtime by using:

    snprintf(character->name, 128, "CJK UNIFIED IDEOGRAPH-%X", codepoint);
    snprintf(character->name, 128, "CUNEIFORM SIGN %s", name);
    // And others

    But my database was still pretty big: 2,486,272 bytes

    Prefix compression

    What is prefix compression? Simple: when two strings share the same prefix, there is no need to save it twice.

    Example:

    LATIN SMALL LETTER C WITH CEDILLA
    LATIN SMALL LETTER E WITH GRAVE

    There are many previous studies on how to store this, because a filesystem typically has many files that start with the same string. But the Google File System one captured by attention: https://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf.

    1. Sort the strings
    2. Identify a common prefix
    3. Store only diffing parts
    4. Save the length of the previous string

    Let’s take a real example. We sort some strings found in the file:

    0. LATIN SMALL LETTER C WITH CEDILLA
    1. LATIN SMALL LETTER E WITH GRAVE
    2. LATIN SMALL LETTER E WITH ACUTE
    3. LATIN SMALL LETTER E WITH CIRCUMFLEX

    We calculate previous prefix and store the length.

    0. 0  | LATIN SMALL LETTER C WITH CEDILLA
    1. 19 | E WITH ACUTE
    2. 26 | CIRCUMFLEX
    3. 26 | GRAVE

    So second string is “substring of length 19 of string at previous position (0) concatenared with string at position 1”

    "LATIN SMALL LETTER " + "E WITH ACUTE"
    "LATIN SMALL LETTER E WITH ACUTE"

    First string is stored in full. The others refer to the previous one. Let’s imagine that SQLite uses only 8 bits for that integer. So the savings will be 19 + 26 + 26 – 1 – 1 – 1 = 68 bytes. This is what Google uses with GFS, SSTables, and Bigtable, and it’s a simple, performant way to save space.

    Is this the best for Mojibake? No. On Mojibake you can access a random entry from the database. Example, by using the WASM magic: https://mojibake.zaerl.com/?function=mjb_codepoint_character&codepoint=128

    Since each entry depends on the previous entry’s prefix, you must decompress sequentially from the start up to position U+128 and it will be a waste of time.

    Position 0:  Direct access ✓
    Position 1:  Rebuild from 0 → 1
    Position 2:  Rebuild from 0 → 1 → 2
    Position N:  Rebuild from 0 → 1 → 2 → ... → N  ✗ Slow!

    How SSTables solve it when there are millions of rows? It simply stores full keys at regular intervals, so no need to read N rows. Let’s imagine an “interval” of three.

    LATIN SMALL LETTER C WITH CEDILLA // Checkpoint
    LATIN SMALL LETTER E WITH GRAVE // 1. 19 | E WITH GRAVE
    LATIN SMALL LETTER E WITH ACUTE // 2. 19 | E WITH ACUTE
    LATIN SMALL LETTER E WITH CIRCUMFLEX // Checkpoint
    ...

    Mojibake saves data one time, read it multiple times. So I decided to use a “prefix dictionary table” approach.

    CREATE TABLE IF NOT EXISTS prefixes (
        id INTEGER PRIMARY KEY,
        name TEXT NOT NULL
    );
    
    CREATE TABLE IF NOT EXISTS unicode_data (
        codepoint INTEGER PRIMARY KEY,
        -- multiple columns
        prefix INTEGER -- a foreign key to the prefixes table
    );

    The new query is slightly more complex:

    SELECT
        u.codepoint,
        CASE WHEN p.name IS NOT NULL THEN p.name || u.name ELSE u.name END as name,
        -- multiple columns
        FROM unicode_data u LEFT JOIN prefixes p ON u.prefix = p.id WHERE u.codepoint = ?

    In other words:

    1. I read common prefixes
    2. I create the prefix table
    3. I save on unicode_data the prefix
    4. I concatenate the two strings at runtime, if needed

    On finding the best set of prefixes to save

    This is the most complex thing to do. When does saving a prefix save you space? It depends on how much SQLite takes for:

    1. A new row on the prefix table (plus index)
    2. An integer on the unicode_data table (instead of a null)

    Does this take less space? The only way to be sure it does is to… try. SQLite is very, very performant when it comes to optimization. Let’s see what I thought was the best in the new PrefixCompressor class.

    Keep in mind that the algorithm is not meant to be run multiple times, and so it is not optimized for space or speed.

    First step. For every Unicode character (~53k) name of length N we save a map for every single prefix (a candidate) of length P (4, default). 0(N^2) run and space complexity

    String length NCalculationTotal characters
    N = 5(5)5
    N = 75 + 6 + 718
    N = 105 + 6 + … + 1040 (!)

    Lot of RAM, but like I said it’s not a problem. On Unicode 17 UnicodeData.txt file there are a total of 405,878 bytes on name columns, and names mean length is ~11. For all the prefixes we save a set of usage information.

    We then greedly select the prefixes and calculate the benefit of adding that prefix. Finally we sort prefixes by length descending for greedy matching (longest first).

    Conclusion

    MetricBytes
    Original size2,486,272 bytes (~2.37 MB)
    New size1,925,120 bytes (~1.84 MB)
    Space saved561,152 bytes (~548 KB)
    Reduction22.6%

    Was it worth it? Yeah, it was fun.

  • It’s Not Wrong that (for HN) “🤦🏼‍♂️”.length == 36

    Hey! Unintentional clickbait! I am not talking about how a space character has length 36 in Hacker News! If you are coming here from HN the above 🤦🏼‍♂️ emoji have been replaced with a space!

    Edit: Success! HN has renamed my entry to It’s Not Wrong that (for HN) “[facepalm emoji]”.length == 36. At least better that the JS \u{HEX} one

    A couple of days I published a pretty innocent post to HN. The source article was talking about all the various escamotages techniques used to create new emojis.

    I noticed after posting it that the emoji have been replaced with a “ “ character. I was pretty sure to have seen emojis in the past on HN titles, so I thought that maybe it was a first level filter of some sort.

    Today I checked again and it was pretty funny to see the actual renaming done to have it stay in our beloved 80 columns.

    It’s not wrong that “\u{1F926}\u{1F3FC}\u200D\u2642\uFE0F”.length == 7 (2019)

    Ah, and copy-pasting this post URL on mobile Safari, shows it this way:

    https://zaerl.com/2025/08/24/its-not-wrong-that-for-hn-🤦🏼♂%EF%B8%8F-length-36/

    🙂 <- a simple one

    Edit: [U+1F642 slightly smiling face emoji] <- a even simpler one?

  • Shrink SQLite amalgamation

    In Mojibake, the low-level Unicode library I am writing the first rule is: be small. I am using the SQLite amalgamation to index the hundred of thousands on codepoints/characters/etc.

    These are the numbers on SQLite 3.50.2, standard amalgamation.

    sqlite3.c 8,9MB
    sqlite3.h 646KB

    Once built with a very basic run of clang:

    libmojibake_sqlite.a 1.6MB

    We can do better because in Mojibake I don’t do a lot of things at run-time.

    How to omit features you want

    There are ~70 features you can omit to have by using compile-time SQLITE_OMIT_* options. The important thing to understand is that you can omit something and it appears to work but it does not.

    Why? It’s pretty simple. The last step of the make call of a standard SQLite do produces the sqlite3.c and sqlite3.h with all the code found in the +100 .c files. So, if you don’t omit something before this process is done that part of code will be still there despite the flag you send when compiling the amalgamation.

    Let’s make an example. One of the must-have OMIT flags the SQLite team recommend you is the SQLITE_OMIT_DECLTYPE one. By sending it as a -D will #define it and your code will act the correct way.

    SQLITE_ENABLE_ORDERED_SET_AGGREGATES instead is another thing. It changes the LALR(1) parser tables. You can set it in the amalgamation, but it will not work. You must define it before the amalgamation is created.

    OPTS vs OPT_FEATURE_FLAGS vs CFLAGS

    Imagine you don’t want the JSON library. You need to use SQLITE_OMIT_JSON`. In the official documentation you can find this:

    Special versions of the SQLite amalgamation that do work with a predetermined set of SQLITE_OMIT_* options can be generated. To do so, make a copy of the Makefile.linux-gcc (now is called Makefile.linux-generic) makefile template in the canonical source code distribution. Change the name of your copy to simply “Makefile”. Then edit “Makefile” to set up appropriate compile-time options. Then type: make; make sqlite3.c

    The Makefile accept CFLAGS so you can think this is ok:

    make clean
    make CFLAGS="-DSQLITE_OMIT_JSON" sqlite3.c

    But it does not work. The size is the same. This is because you are sending the compiler flags to the script that is generating the amalgamation, but they must be passed to the LEMON parser generator and the mkkeywordhash tool as well.

    The solution can be seen in main.mk#L271.

    1. OPTS: used to specify additional compiler flags directly on the command line when invoking make.
    2. OPTIONS: similar to OPTS, but an historical way. It’s a value appended to OPT_FEATURE_FLAGS
    3. OPT_FEATURE_FLAGS, the central variable that aggregates everything. Usually built by the configure script

    Add the OMIT flag during amalgamation creation.

    make sqlite3.c OPTS="-DSQLITE_OMIT_JSON"

    And send the same -DSQLITE_OMIT_JSON later when you build the sqlite3.c file in your target executable. This will affect all the stages.

    The conclusion

    I don’t do a lot of stuff at run-time in Mojibake. For example, I don’t write anything but only read so I can remove a lot of stuff. I crafted a huge list of flags to have. Now these are the numbers

    sqlite3.c 8,9MB -> 8.8MB
    sqlite3.h 646KB (it does not change)
    libmojibake_sqlite.a 1.6M -> 1.2M

    I can probably even add more flags to the omit list and have better numbers.

    And by playing with this I also found a bug that the SQLite team quickly fixed: https://sqlite.org/forum/forumpost/5312f3d82e. Not something you see everyday eh?

    To defeat an AI, a screwdriver is enough.

  • Perl, my old friend

    I was a Perl programmer many years ago. I remember having a program called good.pl, as in “good morning,” that at login runs my terminal, my text editor, SVN, the browser, etc.

    The 80-character line was a big deal, and with Perl, it was easy; that’s one of the reasons I really liked it.

    I will examine one of my old Perl 5.* script (cw.pl) to see how easy it is for me to remember how it works.

    After an initial ten seconds, when I need to erase the $var PHP syntax, I am ready. But first ask an AI what happened in the latest years by making the code more modern.

    What are the most interesting changes

    The AI added a lot of things, like renaming variables, new subroutines, etc. Let’s see only the most interesting one.

    Added Pragmas

    The script now has some use‘s at the top, Python style. Good stuff.

    Improved Variable Handling

    All variables are now properly declared with my. I like this. In my old script first time you access a “global” variable it was initialized (if I remember well)

    New File Handling

    Bareword filehandles has been replaced by lexical filehandles. I like it.

    The say feature

    We have a new say feature. I like it, not the name, but it’s a good addition.

    The foreach “my” declarations

    You can now using my in foreach declarations? I don’t remember if it was a thing years ago and I simply didn’t use it, but is a must have.

    Proper file declaration error checking

    # open(INPUTFILE, $temp_name) || warn "Could not open $temp_name\n";
    open(my $fh, '<', $filename) or die "Could not open '$filename': $!\n";

    I like the three-argument form of open.

    Conclusions

    It was a nice trip down memory lane. I will study modern Perl the next days, for fun.

    Until next time.

  • About HolyC

    I was always fascinated by the idea that just one man could have created TempleOS. Building an OS alone in 10 years is like building a one-man-built skyscraper. I’ve decided to try to understand HolyC, the C “dialect” the OS is written, even for fun, because I am sure I will never be able to create what Terry A. Davis has done.

    This is a little experiment when I document the steps I’ve followed in this first approach to the TempleOS source code. I know it has already been studied, and I can find tons of documentation online. But this isn’t funny.

    Where to start

    I am an experienced C/C++ programmer, so I’m confident it will be very funny. The TempleOS source code is in the Public Domain, and you can find it at https://github.com/cia-foundation/TempleOS.

    Let’s start with something simple. I’ve found a file called Kernel/QSort.HC that, on a rapid look, seems to be an implementation of Quicksort. The Quicksort algorithm is one of the very first you learn when you start talking about sorting stuff; that’s why it’s a good start.

    From the file I can extrapolate four functions:

    U0 QSortI64(I64 *base,I64 num, I64 (*fp_compare)(I64 e1,I64 e2));
    U0 QSort2a(U8 **base,I64 num,I64 (*fp_compare)(U8 **_e1,U8 **_e2));
    U0 QSort2b(U8 *base,I64 num, I64 width, I64 (*fp_compare)(U8 *e1,U8 *e2),U8 *tmp);
    U0 QSort(U8 *base,I64 num, I64 width, I64 (*fp_compare)(U8 *e1,U8 *e2));

    Quick considerations

    1. U0 seems to be a NULL (unsigned zero?).
    2. U8 is a char of 8 characters.
    3. I64 is a 64-bit integer (and so on).
    4. Pointers appear the same as C.

    TempleOS is a 64-bit-only OS, so it makes sense to name the variable with the dimensions in bit directly. Other considerations

    1. pivot=base[num/2]; Integer division is truncated toward zero, like in C.
    2. MAlloc(width*2) and Free are the names for the corresponding malloc and free stdlib functions.

    The code now reports about a: Maybe, look at $LK,"::/Demo/MultiCore/MPRadix.HC"$. The $LK ... $ is probably some smart link you can select to jump to the other file. It can stand for LinK. The fact that it’s a string surrounded by two characters you don’t usually find in a C file can help select it. But let’s move on to Demo/MultiCore/MPRadix.HC.

    On to the first demo

    Something new in this file immediately caught my eye.

    1. HolyC supports C++ one-line comments (C does it, too, but only since from C99).
    2. There is a no_warn dummy; it probably mutes the compiler. The dummy variable is not used inside the function.
    3. "$$GREEN$$QSort$$FG$$\n"; probably write something in the console.
    4. "Time:%9.6f\n",tS-t0; it’s a printf without the declaration of the function? Wow!
    5. D(arg2+NUM/4); A debug output?

    I had already lost three functionalities on my way, so I decided to clone the repository and search the code broadly. I found the D function very quickly. As the comment says, it’s a debug function.

    Now, up to point 3, the $$ syntax. As I imagined, it’s used all over the place. But I founded:

    1. A DocPrint(doc,"$$LTBLUE$$");
    2. And a DocPrint(doc,"$$MU,\"%d\",LE=%d$$\n",i,i);

    So, it is a printf, and the format is similar. But I can see a simple dangling string in the code, which is interesting. During my searches, I also found that DocBottom is the same as calling DocBottom(). If you have no parameters to pass to a function, you can save two parentheses characters. Cool!

    After searching and digging, I arrived at the lexer. You don’t need to write printf to output or use strange, non-mnemonic ANSI colors. I find this fascinating and wonder how complex the C LARL will become.

    Searching for a complete program

    I decided to search for a complete program, and given my accumulated knowledge, I searched for “I32 main(“. Nothing. “I64 main(“, nothing again. I don’t want to search for the result online; in this little experiment, I want to understand the code from the OS code, not from any external document.

    U0 main(. I found it; the main() function returns NULL and does not accept arguments. In the meantime, I saw a file called HolyC.DD, the documentation of HolyC? Yes, I could have searched for documentation as the first step, but like I already said, it’s not funny. Digging through the kernel files is interesting!

    The HolyC documentation file

    The file starts with a:

    $WW,1$$FG,5$$TX+CX,"HolyC"$$FG$
    
    * See $LK,"::/Doc/CompilerOverview.DD"$.
    
    * See $LK,"Scoping and Linkage",A="FI:::/Doc/ScopingLinkage.DD"$ for details on $FG,2$extern$FG$, $FG,2$import$FG$, $FG,2$_extern$FG$, $FG,2$_import$FG$, etc.

    Like I thought, the $$LK,"path"$$ is a link to a filesystem. This is

    Built-in types include $FG,2$I0,I8,I16,I32,I64$FG$ for signed 0-8 byte

    Like I thought as well. I32 is like writing int32_t. Having HolyC built-in types in C will be easy work. Just a tiny list of type definitions:

    #include <stdint.h>
    
    typedef int16_t I16;
    typedef int32_t I32;
    // and so on.

    Now the good part:

    Function with no args, or just default args can be called without parentheses.

    Default args? Like in PHP? I didn’t notice it! And better:

    Default args don't have to be on the end.

    It’s not like PHP. So this is working code:

    // The function: I64 Dir(U8 *files_find_mask,Bool full)
    Dir("*")
    Dir();
    Dir;
    
    // Default args not at the end
    U0 Test(I64 i=4,I64 j,I64 k=5) {
        // ...
    }
    
    U0 DemoHolyC(U8 drv,U8 *fmt,U8 *name,I64 age) {
        // This is sent to PutChars()
        "Hello World!\n";
    
        // To Print()
        "%s age %d\n",name,age;
    
        // An empty string followed by a string (fmt) is a string
        "" fmt,name,age;
    
        // To PutChars(). Same behavior as before
        '' drv;
    
        // To PutChars()
        '*';
    }

    The main() function

    I searched for the main() function, and I didn’t need to because I just found from this file that:

    Any code outside of functions gets executed upon start-up in order.

    Like in a lot of scripting languages. And this is nothing compared to this:

    I64 AddNums(...)
    {
      I64 i,res=0;
      for (i=0;i<argc;i++)
        res+=argv[i];
      return res;
    }

    Every function and any code outside a function can access parameters and the count from the global argc and argv! And also:

    1. The if short-syntax 13<=age<20.
    2. The switch cases automatically start from zero and increment by one, no need to specify the number.
    3. The switch cases can be nested.
    4. All values are extended to 64-bit when accessed. Intermediate calculations are done with 64-bit values.
    5. And so on.

    Farewell Terry

    I then decided to stop. Such a naive analysis is not the way to study the TempleOS or pay respect to him. Having mental problems is one of the worst things that can happen to you.

    I have drug-resistant epilepsy, and programming is one of the few things that keep a smile on my face. Today, I’ve smiled a lot every time I saw something HolyC has, and C does not.

    Until next time.

  • Add a language construct to PHP, part 1

    These days, I’m studying the PHP core to see the various techniques used. This is part 1 of our journey, where we will add a patch to an existing construct. Approaching such a big project takes work.

    Adding a new function is pretty simple. Here is a quick example written in C taken from the Zend Engine official documentation:

    PHP_FUNCTION(test_scale)
    {
        double x;
    
        ZEND_PARSE_PARAMETERS_START(1, 1)
            Z_PARAM_DOUBLE(x)
        ZEND_PARSE_PARAMETERS_END();
    
        RETURN_DOUBLE(x * 2);
    }

    The PHP Internal Book is a great start. You can read it to understand how things work under the hood.

    But how about adding a new language construct?

    First of all, what are we talking about? Simple. It is something like an echo. From the documentation

    echo is not a function but a language construct. Its arguments are a list of expressions following the echo keyword, separated by commas, and not delimited by parentheses. Unlike some other language constructs, echo does not have any return value, so it cannot be used in the context of an expression.

    Start from the very beginning before digging too much.

    Make it start (on MacOS)

    I cloned the repository from https://github.com/php/php-src to https://github.com/zaerl/php-src and see if I could compile it.

    ./buildconf
    ./configure --enable-debug

    configure: error: Please specify the install prefix of iconv with --with-iconv=

    Ok, not a problem. Install libiconv and proceed.

    ./configure --enable-debug --with-iconv=/opt/homebrew/opt/libiconv/

    Everything went smoothly. Next step I checked how many cores my computer has:

    sysctl -n hw.ncpu
    14

    Now, let’s do it with the power of parallel processing.

    make -j14
    Build complete.
    Don't forget to run 'make test'.

    I then checked if it was true:

    ./sapi/cli/php --version
    PHP 8.4.0-dev (cli) (built: May 13 2024 09:03:04) (NTS DEBUG)
    Copyright (c) The PHP Group
    Zend Engine v4.4.0-dev, Copyright (c) Zend Technologie

    Now try if the tests suite does compile.

    make TEST_PHP_ARGS=-j14 test

    18,915 functional tests later, I got just one failing:

    DOMNode::isEqualNode() [ext/dom/tests/DOMNode_isEqualNode.phpt]

    I don’t think this is such a problem. So let’s consider this a success and move on.

    A new construct, but what?

    PHP already has a lot of operators and a lot of reserved keywords. So let’s choose one that, in order of importance:

    1. Do not break preexisting tests.
    2. It is similar to a preexisting one. I choose echo.
    3. It isn’t too complicated.
    4. It serves some purpose, and it’s not a joke.

    So, I decided to create a new one called always. It is a construct that checks if a value is true, and if it is not, it spawns an exception.

    Let’s start it slow

    PHP uses the Zend Engine under the hood, which uses re2c. Adding a new construct means:

    1. Update the lexer.
    2. The parser.
    3. The compiler.
    4. The virtual machine.

    I immediately abandoned the idea of doing something in an extension, Zend extension. I’m pretty sure it’s impossible to do all this.

    You can modify the AST tree, which “allows you to modify the AST after it is parsed and created,” but it’s outside the scope of this post here. And not enough funny IMHO.

    Start hacking and:

    git checkout -b experimental/step-1

    We will make a small patch to echo in this first part to make us comfortable with the codebase and not just to serious stuff.

    We will add:

    1. A new php.ini configuration called echoln.
    2. If echoln is true than echo will append a \n to the output.
    3. A functional test that ensure it’s true.

    The lexer

    The first pass it to find where echo is declared and how. PHP, like many other interpreters, uses Lex/Yacc kind of files to generate the code. On the Zend/zend_language_scanner.l Lex file we find the token at line 1,532:

    <ST_IN_SCRIPTING>"echo" {
    	RETURN_TOKEN_WITH_IDENT(T_ECHO);
    }

    On Zend/zend_language_parser.y parser, the token is declared at line 121.

    %token <ident> T_ECHO          "'echo'"

    We will use T_ECHO as the source of truth in the code. The only strange syntax in the YACC file is a %precedence keyword. That’s what I was used to:

    1. %left
    2. %right
    3. %noassoc

    … sometimes, when trying to solve a conflict, precedence suffices. In such a case, using %left, %right, or %nonassoc might hide future (associativity related) conflicts that would remain hidden.

    That makes sense. I like the idea.

    The parser

    Digging through the parser file bought me to this declaration at line 1,102:

    echo_expr:
    	expr { $$ = zend_ast_create(ZEND_AST_ECHO, $1); }
    ;

    The statement is compiled in at line 10,616 of the Zend/zend_compile.c file.

    case ZEND_AST_ECHO:
    	zend_compile_echo(ast);
    break;

    The C function

    PHP does not load and recompile .php files for every request but use opcache. Now we found the function that emits the ZEND_ECHO opcode, found at line 5,397:

    static void zend_compile_echo(zend_ast *ast) /* {{{ */
    {
    	zend_op *opline;
    	zend_ast *expr_ast = ast->child[0];
    
    	znode expr_node;
    	zend_compile_expr(&expr_node, expr_ast);
    
    	opline = zend_emit_op(NULL, ZEND_ECHO, &expr_node, NULL);
    	opline->extended_value = 0;
    }
    /* }}} */

    And finally, the C function that does the actual print at line 1,679 of the Zend/zend_vm_def.h file:

    ZEND_VM_HANDLER(136, ZEND_ECHO, CONST|TMPVAR|CV, ANY)
    {
    	USE_OPLINE
    	zval *z;
    
    	SAVE_OPLINE();
    	z = GET_OP1_ZVAL_PTR_UNDEF(BP_VAR_R);
    
    	if (Z_TYPE_P(z) == IS_STRING) {
    		zend_string *str = Z_STR_P(z);
    
    		if (ZSTR_LEN(str) != 0) {
    			zend_write(ZSTR_VAL(str), ZSTR_LEN(str));
    		}
    	} else {
    		zend_string *str = zval_get_string_func(z);
    
    		if (ZSTR_LEN(str) != 0) {
    			zend_write(ZSTR_VAL(str), ZSTR_LEN(str));
    		} else if (OP1_TYPE == IS_CV && UNEXPECTED(Z_TYPE_P(z) == IS_UNDEF)) {
    			ZVAL_UNDEFINED_OP1();
    		}
    		zend_string_release_ex(str, 0);
    	}
    
    	FREE_OP1();
    	ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION();
    }

    This function:

    1. If the z parameter passed is a string is a string print it with zend_write.
    2. Otherwise, an attempt to convert to a string is performed using __zval_get_string_func.

    It’s interesting to see the infamous “Array to string conversion” warning in this function. The echo function uses zval_get_string_func and not zval_try_get_string_func. So, the value is never converted to a string, but the ZEND_STR_ARRAY_CAPITALIZED (Array) constant is used instead.

    The code is much cleaner than I thought it could have been, even with historical constructs like echo.

    Add the new php.ini directive

    Before changing the code of the ZEND_ECHO function, we need to add a new php.ini configuration directive. Digging through the code I proceeded to add:

    1. Add echoln to main/main.c PHP_INI section.
    2. Add echoln to main/php_globals.h _php_core_globals struct.

    I ran make and make test, and nothing exploded. Good start.

    Add new section to ZEND_ECHO

    It’s time now to modify the function and add our new section:

    ZEND_VM_HANDLER(136, ZEND_ECHO, CONST|TMPVAR|CV, ANY)
    {
    	USE_OPLINE
    	zval *z;
    
    	SAVE_OPLINE();
    	z = GET_OP1_ZVAL_PTR_UNDEF(BP_VAR_R);
    
    	if (Z_TYPE_P(z) == IS_STRING) {
    		zend_string *str = Z_STR_P(z);
    
    		if (ZSTR_LEN(str) != 0) {
    			zend_write(ZSTR_VAL(str), ZSTR_LEN(str));
    		}
    	} else {
    		zend_string *str = zval_get_string_func(z);
    
    		if (ZSTR_LEN(str) != 0) {
    			zend_write(ZSTR_VAL(str), ZSTR_LEN(str));
    		} else if (OP1_TYPE == IS_CV && UNEXPECTED(Z_TYPE_P(z) == IS_UNDEF)) {
    			ZVAL_UNDEFINED_OP1();
    		}
    		zend_string_release_ex(str, 0);
    	}
    
    	bool echoln = INI_BOOL("echoln");
    
    	if (echoln) {
    		zend_write("\n", 1);
    	}
    
    	FREE_OP1();
    	ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION();
    }

    Test the results

    All preexisting tests should work without touching anything. We then add two new files to test our new functionality:

    Zend/tests/echoln/001.phpt

    --TEST--
    Basic "echoln" test with default value.
    --FILE--
    <?php
    echo "Hello World!";
    ?>
    --EXPECT--
    Hello World!

    Zend/tests/echoln/002.phpt

    --TEST--
    Basic "echoln" test
    --INI--
    echoln=1
    --FILE--
    <?php
    echo "Hello World!";
    ?>
    --EXPECT--
    Hello World!
    
    

    The second one sets our directive to true and checks if the output ends with a new line (notice the last empty line).

    Conclusions

    Changing PHP internals is easy! You can get all the changes here: Add a language construct to PHP, part 1. Next time, we will continue our journey by adding our always token to the grammar, an opcode generator, and a brand-new VM function.

    In the meantime, happy hacking!

  • 28 arguments are required

    Today, I saw a PHP error you don’t see everyday:

    Fatal error: Uncaught ArgumentCountError: 28 arguments are required, 1 given in…

    You heard it right. There was somewhere a function that needed 28 arguments. Well, not exactly that number. Fortunately, the PHP stack trace is kind enough to give you enough information to solve the arcane.

    It seems like an innocent typo, right? A printf when an echo is enough and faster. No, it isn’t. The main problem here is that things have changed under the hood, and sometimes, small changes can lead to bad errors.

    The printf function has changed in PHP 8.0.0.

    As of PHP 8.0.0, a ArgumentCountError is thrown when less arguments are given than required. Prior to PHP 8.0.0, false was returned and a E_WARNING emitted instead.

    So what happened here was that the user had 28 ‘%’ format specifiers in its text. Maybe a long URL-encoded string? Who knows.

    I tried to remember the most extended function signature I encountered and then recalled the famous WideCharToMultiByte.

    Not even near 28 arguments.