8 ms·

I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. I suspect strcmp() wasn't expected to

I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. I suspect strcmp() wasn't expected to provide order on non-ASCII data when that code was written, with char defined as u8. The original K&R code just subtracts the two (signed) chars too: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/gen/strcmp.c https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/g...

kentonv 4y ago
Subtracting two chars produces an `int`. C generally promotes all smaller types to `int` before doing arithmetic, and `int` is required to be at least 16 bits. So I think the code you linked is correct?
fanf2 4y ago
That old C code relies on integer promotion to avoid the overflow problems that occurred in the m68k asm.
- _kst_ 4y ago
  Exactly. C has no arithmetic operations on types narrower than int and unsigned int. This bug (which involves subtracting 8-bit values and yielding an 8-bit result) could only happen in assembly language (or in an exotic C implementation where CHAR_BIT > 8 and int is 1 byte, or in C code that uses casts to deliberately create the bug).
loeg 4y ago
> I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. No. As the article notes, there's also a bug when char is signed (the subtraction may overflow, which is UB for signed char, and additionally produces the wrong result even assuming defined overflow). It's just more obvious when char is unsigned.
- pavon 4y ago
  Plain ASCII is 7-bit so it won't overflow with signed char. There are many extensions that use that extra bit to increase the number of characters, but they aren't ASCII, they are ISO 8859-*, or ANSI, or UTF-8 etc.
  - loeg 4y ago
    As the article notes, Linux does not validate strings for 7-bit cleanness, so the routine needs to work on strings that use the high bit.
  - layer8 4y ago
    The problem is not just that it results in a wrong order for 8-bit encodings, but that it doesn’t result in a well-defined order at all. For example, you get: -2 > 127 > 64 > -2 This can make sorting algorithms loop infinitely or crash.
    - koverstreet 4y ago
      Buggy comparison functions that don't correctly define an ordering is one of my favorite classes of bugs.
      - layer8 4y ago
        It’s also something that is difficult to unit-test.
- jabl 4y ago
  > UB for signed char Signed overflow is undefined in C, but this was implemented in ASM. I'm not familiar with the m68k isa, but I'd be very surprised if it doesn't define signed values to wraparound as is natural for a two's complement implementation.
deleted 4y ago
[deleted]

kentonv 4y ago

Subtracting two chars produces an `int`. C generally promotes all smaller types to `int` before doing arithmetic, and `int` is required to be at least 16 bits. So I think the code you linked is correct?

fanf2 4y ago

That old C code relies on integer promotion to avoid the overflow problems that occurred in the m68k asm.

_kst_ 4y ago
Exactly. C has no arithmetic operations on types narrower than int and unsigned int. This bug (which involves subtracting 8-bit values and yielding an 8-bit result) could only happen in assembly language (or in an exotic C implementation where CHAR_BIT > 8 and int is 1 byte, or in C code that uses casts to deliberately create the bug).

loeg 4y ago

> I dispute that it has "always" been broken -- the bug is to do with ordering non-ascii input data, when char is unsigned. No. As the article notes, there's also a bug when char is signed (the subtraction may overflow, which is UB for signed char, and additionally produces the wrong result even assuming defined overflow). It's just more obvious when char is unsigned.

pavon 4y ago
Plain ASCII is 7-bit so it won't overflow with signed char. There are many extensions that use that extra bit to increase the number of characters, but they aren't ASCII, they are ISO 8859-*, or ANSI, or UTF-8 etc.
- loeg 4y ago
  As the article notes, Linux does not validate strings for 7-bit cleanness, so the routine needs to work on strings that use the high bit.
- layer8 4y ago
  The problem is not just that it results in a wrong order for 8-bit encodings, but that it doesn’t result in a well-defined order at all. For example, you get: -2 > 127 > 64 > -2 This can make sorting algorithms loop infinitely or crash.
  - koverstreet 4y ago
    Buggy comparison functions that don't correctly define an ordering is one of my favorite classes of bugs.
    - layer8 4y ago
      It’s also something that is difficult to unit-test.
jabl 4y ago
> UB for signed char Signed overflow is undefined in C, but this was implemented in ASM. I'm not familiar with the m68k isa, but I'd be very surprised if it doesn't define signed values to wraparound as is natural for a two's complement implementation.

deleted 4y ago

[deleted]