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 10:47:09 -0700 Organization: A noiseless patient Spider Lines: 160 Message-ID: <86h5jfsvvm.fsf@linuxsc.com> References: <10uks4f$1dqo$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> <86ld8srnq9.fsf@linuxsc.com> <1190t4j$1u067$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 23 Sep 2026 17:47:10 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2106619"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/UzhVGJNo04t21RkfxktHC4lMNK4ldq8Y="; posting-host="e854bcdde9edbfa449147ac38d1c2707" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:Pp6iyaPQr66XNUcMhIM3xp0sxys= sha1:GCmLNO1+VKb1Qc36x4RGZfQjZf4= sha256:diDFZFvaPC4SEMdZJvfhYx2G1QiDR6JXzVtC2diAAkU= sha1:EI9Yxsk0UCdoj8mfN8iWPUh6kng= sha256:CJ06xDiQHa3gFbEYevh1zcwhNucPXw75ZBb4EQiP2e0= Xref: csiph.com comp.arch:118155 Terje Mathisen writes: > Tim Rentsch wrote: > >> 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 > > As my original comments stated, in both Perl and Rust n % BASE will > always return a positive remainder when the BASE is positive. The original post did have a comment saying that the remainder would be positive (i.e., non-negative), but it didn't mention either Perl or Rust. It's because of this kind of possible incongruities that I asked for a C version. > I.e not like C where I believe this used to be implementation-defined. In the original C standard division and remainder were indeed implementation-defined for negative operands. That was changed in C99. >> 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). > > Right! > > I know that both divisions should return the same result, with the > second intentionally have zero remainder, but that does leave the door > open for an optimized version. Thanks! The point is that the two divisions can give different results, even when both operands are positive -- one rounds down, the other might round up. >>> 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; >> } > > I'll see if this translates, and if it is faster... Please tweak it up to improve any platform-specific weaknesses that might be there. I'm sure you are better at doing that than I am (plus you are running on hardware with different performance characteristics).