Hacker News Reader

Comment by im3w1l | Hacker News Reader

A fairly common special case of printing integers is printing all integers from 0 to N. In that case you can use a trick: Keep a string representation of the current number and increment the string representation.

View on HN

Anyone who has played the old arcade games with fixed-width score counters will have seen this trick in action --- many of those ran on 8-bit processors without multiply or divide instructions, so it was much easier to keep the score as an array of digits and increment those than a binary variable and the equivalent of an itoa() every time it needed to be displayed.

More succinctly, in pseudocode:

    while(++digits[i] > '9')
        digits[i--] = '0';

By starting the increment at the non-rightmost digit, it also allows for easy addition of powers of 10: 10, 100, 1000, etc.

Related to this is binary coded decimal [1]: let each nibble (4 bits) of your integer represent a decimal digit 0-9. Then do your arithmetic in binary, but after each operation run a special CPU instruction to "correct" the result to what it should be in decimal.

[1] https://en.wikipedia.org/wiki/Binary-coded_decimal

There are two BCD formats. Packed (what you describe) and unpacked (where only a single digit is stored per byte). Unpacked seems to have the advantage that converting to ASCII is just a matter of setting two bits, and converting from ASCII is just a matter of masking those out.

I found this example very illuminating

    sub    AH,AH    ; clear AH
    mov    AL,'6'   ; AL := 36H
    add    AL,'7'   ; AL := 36H+37H = 6DH
    aaa             ; AX := 0103H
    or     AL,30H   ; AL := 33H

because aaa instruction clears the high nibble of AL, it works with either unpacked BCD or with ASCII (but always outputs BCD).

http://service.scs.carleton.ca/sivarama/asm_book_web/Instruc... (page 8)

But iiuc aaa didn't make it in the transation to 64bit processors.

The Game Boy CPU kept track of nibble overflows and had an instruction called DAA to adjust the packed BCD value in the A register after an arithmetic operation. If you disable this instruction in an emulator many games start counting your score in hexadecimal (Tetris even has the sprites A to F interestingly, so you actually get your full score displayed correctly).

The Game Boy "had" this DAA instruction from its CPU, a variant of the Z80. This trick may well have been used also on some Amstrad CPC games also, then.

Indeed, the Z80 itself, which people like us know because it was very common in 8bit home computers, is an enhancement of the Intel 8080, which itself is an ancestor of the current Intel CPUs.

Incidentally, Z80 CPUs are still manufactured 40+ years later ( https://en.wikipedia.org/wiki/Zilog_Z80 ) and benefit from modern C compilers like SDCC and software development environments like z88dk or the one I wrote for the Amstrad CPC: https://github.com/cpcitor/cpc-dev-tool-chain (written for Linux and tools like GNU make, wget, etc).

That said, writing C code that compiles to packed BCD and the use of DAA at assembly level does not seem very practical. If few numbers are manipulated, unpacked BCD is simpler (closer to string, less code to handle) both in assembly and in C.

Some CPUs like the Saturn from Hewlett-Packard [1] are designed for BCD. Though they can perform binary operations, registers are structured for 64-bit floating point operations with a 4-bit wide bus and nibble-granularity addressing of register nibbles: 1 sign, 12 mantissa, 3 exponent.

[1] https://en.wikipedia.org/wiki/HP_Saturn

GNU seq uses this trick:

slow path:

    seq -f '%.1f' inf | pv > /dev/null
     ...[  12MiB/s]

fast path:

    seq inf | pv > /dev/null
     ...[ 491MiB/s]

Can you explain that a bit more? I know "seq", but am unsure what your examples are illustrating. Thanks!

-f specifies a format, so it can't use the specialized itoa implementation, but probably just uses printf.

This is a common case? Besides educational exercises, why? I would have guessed most printed integers are random ID numbers, prices, database foreign keys, etc.

Line numbers in less(1) or GitHub. Row numbers in Excel, Pandas, R, etc.

The most common way to label rows is with sequential numbers.

FWIW, in a file with 1,000,000 lines, the best-of-3 time for "less filename > /dev/null" is:

  2.508u 0.152s 0:02.66 99.6%	0+0k 0+0io 0pf+0w

and the best-of-3 time for "less -N filename > /dev/null" is:

  2.568u 0.159s 0:02.73 99.2%	0+0k 0+0io 0pf+0w

That is, it doesn't seem like printing sequential is the limiting factor in performance.

Checking the source code, it does not appear to use knowledge of the previous output index in order to save time. The relevant code is:

        static int
  iprint_linenum(num)
        LINENUM num;
  {
        char buf[INT_STRLEN_BOUND(num)];

        linenumtoa(num, buf);
        putstr(buf);
        return ((int) strlen(buf));
  }

where

  #define TYPE_TO_A_FUNC(funcname, type) \
  void funcname(num, buf) \
          type num; \
          char *buf; \
  { \
          int neg = (num < 0); \
          char tbuf[INT_STRLEN_BOUND(num)+2]; \
          register char *s = tbuf + sizeof(tbuf); \
          if (neg) num = -num; \
          *--s = '\0'; \
          do { \
                  *--s = (num % 10) + '0'; \
          } while ((num /= 10) != 0); \
          if (neg) *--s = '-'; \
          strcpy(buf, s); \
  }
  
  TYPE_TO_A_FUNC(linenumtoa, LINENUM)

hmm, maybe someone can get a pull request for implementing this optimization :)

While I know you meant that comment in jest, it suggests that I wasn't clear enough.

My implicit argument is that there's there's no reason to believe that line counting adds anything more than trivial overhead to the less output, so there's no reason to even consider this optimization, much less getting to the point to make a pull request.

> This is a common case? Besides educational exercises, why?

Sequential IDs permeate everything. Array indicies. Memory offsets. Line numbers, track numbers, page numbers, check numbers... the dates of your daily logs, your calendars... heck, enumeration attacks can be as simple as "what happens when I increment this number by exactly 1 when making this GET request?"

This is so common that there are dedicated ICs to count in base 10.

Reply on news.ycombinator.com