Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.arch Subject: Re: endian history Date: Wed, 23 Sep 2026 08:28:30 -0700 Organization: A noiseless patient Spider Lines: 124 Message-ID: <86ld8srnq9.fsf@linuxsc.com> References: <10uks4f$1dqo$1@gal.iecc.com> <10vnjp6$1df4$1@gal.iecc.com> <10vns1f$3a252$1@dont-email.me> <10vpblp$3mkd1$1@dont-email.me> <10vphh0$3o9jl$1@dont-email.me> <117gj6t$1b95v$2@dont-email.me> <6a9c1c93.39172234@news.eternal-september.org> <117j3es$24qgq$6@dont-email.me> <117n6ho$35j69$1@paganini.bofh.team> <6a9f7664.1891062@news.eternal-september.org> <2026Sep8.125659@mips.complang.tuwien.ac.at> <117pnpg$f179$2@dont-email.me> <11898n9$1nc06$2@dont-email.me> <118d6ld$1tkm9$1@paganini.bofh.team> <118dl5f$37cfv$1@dont-email.me> <118e8kg$3f05h$1@dont-email.me> <868q4zuhz4.fsf@linuxsc.com> <118jitv$1cm6b$1@dont-email.me> <86ik42tcf4.fsf@linuxsc.com> <118uf6m$12tta$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 23 Sep 2026 15:28:33 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2006365"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18MZBwju3twd7/wU2fMlco3pZ5RqT9yxuA="; posting-host="e854bcdde9edbfa449147ac38d1c2707" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:6EqK1lXm6Yz9EtWYhxF4+k0oXBs= sha1:cThK5yYLL67C6lTY+Jxg5ulDYsg= sha256:SRs1pvmMmAj2wjO0hup/vHjQEZi/CeWw+D9zYPA3okE= sha1:co3P6g2rdc1nMQnOvbe2zPh5bw0= sha256:2ja3kn6AYmWsZxj+JHb4HU9/5fKOQ4zstaPCav9FNw4= Xref: csiph.com comp.arch:118152 Terje Mathisen writes: > Tim Rentsch wrote: > >> Terje Mathisen writes: >> >>> Tim Rentsch wrote: >>> >>>> Terje Mathisen writes: >>>> >>>> [...] >>>> >>>>> There was an Advent of Code puzzle in 2022 (last day) where you >>>>> had to work in symmetrical base-5, using '-' and '=' for -1 and >>>>> -2, along with '0', '1', '2'. >>>>> >>>>> You had to parse 113 such numbers, all happened to be positive, >>>>> but they did of course not need to be. With symmetrical encoding, >>>>> there is no extra minus sign in front, just a negative first >>>>> digit. [...] >>>>> Just like decimal, it is a lot easier to convert ascii to binary >>>>> than binary to ascii, the difference between div/mod every digit >>>>> and a single mul. >>>> >>>> Now I'm curious to see how you implemented the binary-to-ascii part >>>> of the problem. Do you still have the code around? >>> >>> Sure: >>> >>> const BASE:i64 = 5; >>> const VALUE:[i8;256] = [ >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,2,0,0,0,0,0,0,0,0,0,0,-2,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, >>> 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; >>> >>> const DIGITS:[u8;5] = [b'0',b'1',b'2',b'=',b'-']; >>> >>> fn tobase(n:i64) -> String >>> { >>> let mut n = n; >>> let mut buf:[u8;32] = [0;32]; >>> let mut p = buf.len(); >>> loop { >>> let r = n % BASE; // positive remainder for positive $BASE >>> let d = DIGITS[r as usize]; >>> n = (n-VALUE[d as usize] as i64) / BASE; // Exact division! >>> p -= 1; >>> buf[p] = d; >>> if n == 0 {break;} >>> } >>> std::str::from_utf8(&buf[p..buf.len()]).unwrap().to_string() >>> } >> >> I'm guessing this code is in Rust. Can I ask you to translate it >> to C for me? Mostly I can guess at the meaning, but as I am only >> a novice with Rust I worry that my guessing would be wrong in some >> cases, and wrong functionality would result. > > The only non-C part here is the final library call to convert a > slice of bytes into a Rust String, the rest is simply what it seems > like for a C programmer. It looks like this statement cannot be right. In C, if n is negative and not a multiple of 5, then n%5 is negative. But after giving r the value of n % BASE, r is used to index an array. That doesn't work if the value of r is negative (to be clear, taking the code as C code). So something is off. >>> In order to be really fast, the compiler has to recognize that >>> both the div and mod should use reciprocal mul (standard), and >>> if possible, only do it once. >>> ... >>> Checking Godbolt: >>> >>> Turns out it is actually generating two IMULs, but it should >>> work for both positive and negative inputs... >> >> I suspect the two multiplys are a consequence of the usual way for >> producing a quotient and remainder: >> >> quotient = n / BASE; >> remainder = n - quotient*BASE >> >> So one of the multiplys is doing a divide by BASE, and the other >> multiply is doing a multiply by BASE. That is plausible anyway. I realized later this idea is wrong. The two IMULs are a result of the two numerators being different, in one case being just n, and in the other case being n-. An IMUL is needed for each of the two numerators (with one being implied for n%BASE). > No, it was actually doing two IMULs by the reciprocal, the multipy > by 5 is just a regular LEA reg,[reg+reg*4] which only takes a > cycle. Here is a way of converting that needs only one mul, although it does have an additional multiply-by-five LEA in the first loop (the name UL is a typedef for unsigned long): char * string_for_balanced_base_5( long x, char *p ){ UL u = x < 0 ? -x : x; UL v = 0; UL k = -1; do k++, v = v*5 + 2; while( v < u ); v += x; *--p = 0; do { *--p = "=-012"[ v%5 ]; v /= 5; } while( k-- > 0 ); return p; }