Bug in BitWordOps Xor function

[Nelson H. F. Beebe]

The WordXor() function in module BitWordOps is almost always wrong,
and if given a 0 argument, it aborts the program run.

The exclusive-OR operation can be implemented in just three hardware
instructions, as discussed in the acclaimed book, Hacker's Delight.
whose details are found at
        
        https://www.math.utah.edu/pub/tex/bib/master.html#Warren:2013:HD

I have used that implementation to write a correct Xor operation for
Modula-2, and verifiable in a companion C implementation exhibited in
these programs and their output:

        % cat testxor32.c
        /*
        ** Test the Hacker's Delight recipe for XOR, in support of debugging
        ** the Modula-2 WordXor() function.
        **
        ** Usage:
        **      cc [ -DMAXTEST=nnn ] testxor32.c && time ./a.out
        */

        #include <stdio.h>
        #include <stdint.h>
        #include <stdlib.h>

        #if !defined(MAXTEST)
        #define MAXTEST 65536   /* run-time: -O3: 5 sec (no opt: 14 sec) on 3 
GHz Intel Xeon */
        #endif

        int
        main(void)
        {
            uint32_t a, b, c, d, e, f;
            uint64_t nerr, ntest;

            nerr = 0UL;
            ntest = 0UL;

            for (a = 0; a < MAXTEST; ++a)
            {
                for (b = 0; b < MAXTEST; ++b)
                {
                    ++ntest;
                    c = a ^ b;

                    d = a | b;          /* see Hacker's Delight, 2nd ed., p. 16 
*/
                    e = a & b;
                    f = d - e;          /* f = XOR(a,b) */

                    if (c != f)
                    {
                        if (++nerr < 6)
                            (void)printf("%#x ^ %#x = %#x: 
hackers_delight_xor() = %#x\n",
                                         a, b, c, f);
                    }
                }
            }

            if (nerr > 0)
                (void)printf("FAILURE: %llu of %llu tests failed\n", nerr, 
ntest);
            else
                (void)printf("SUCCESS: ALL %llu TESTS PASSED\n", ntest);

            return (EXIT_SUCCESS);
        }

Here is the output:

        % cc testxor32.c && ./a.out
        SUCCESS: ALL 4294967296 TESTS PASSED

Here is the Modula-2 comparison of my 3-line implementation of the XOR
operation, versus BitWordOps,WordXor():

        % cat TestWordXor.mod
        MODULE TestWordXor;

        FROM BitWordOps IMPORT WordAnd, WordOr, WordXor;
        FROM CardinalIO IMPORT WriteLongCardinal;
        FROM FIO        IMPORT FlushOutErr;
        FROM NumberIO   IMPORT WriteHex;
        FROM StrIO      IMPORT WriteLn, WriteString;
        FROM SYSTEM     IMPORT CARDINAL32, CARDINAL64;

        CONST MAXTEST = 65536;  (* run-time: -O3: 30 sec (no opt: 40 sec) on 3 
GHz Intel Xeon *)
              MAXREPORT = 10;

        VAR k : CARDINAL;
            a, b, c, d, e, f: CARDINAL32;
            nerr, ntest : CARDINAL64;

        PROCEDURE test(s : ARRAY OF CHAR; a, b, c: CARDINAL32);
        BEGIN
            WriteString(s);
            WriteString('(0x');
            WriteHex(a, 8);
            WriteString(', 0x');
            WriteHex(b, 8);
            WriteString(') = 0x');
            WriteHex(c, 8);
            WriteLn;
            FlushOutErr()
        END test;

        BEGIN
            WriteString('Test of WordXor()');
            WriteLn;
            WriteLn;

            ntest := 0;
            nerr := 0;

            a := 0FFFF0000H;
            b :=  00FFFFFFH;
            c := WordXor(a, b);
            test('WordXor', a, b, c);

            FOR a := 1 TO MAXTEST DO
                FOR b := 1 TO MAXTEST DO
                    INC(ntest);
                    d := WordOr(a, b);           (* see Hacker's Delight, 2nd 
ed., p. 16 *)
                    e := WordAnd(a, b);
                    f := d - e;                  (* f = XOR(a,b) *)
                    c := WordXor(a, b);

                    (* WordXor() is broken in gm2-13 and gm2-14 up to January 
2024 releases *)
                    (* It gets a zero-divide failure if either argument is 0 *)
                    (* Avoid those cases, and report just the failing instances 
*)
                    IF c <> f THEN 
                        INC(nerr);
                        IF nerr < MAXREPORT THEN
                            test('HackersDelightXor', a, b, f);
                            test('WordXor          ', a, b, c);
                            WriteLn;
                            FlushOutErr()
                        END
                    END
                END
            END;

            IF nerr > 0 THEN
                WriteString('FAILURE: ');
                WriteLongCardinal(nerr, 0);
                WriteString(' of ');
                WriteLongCardinal(ntest, 0);
                WriteString(' tests failed')
            ELSE
                WriteString('SUCCESS: ALL ');
                WriteLongCardinal(ntest, 0);
                WriteString(' TESTS PASSED')
            END;

            WriteLn

        END TestWordXor.

Here is the output:

        % gm2 TestWordXor.mod && ./a.out
        Test of WordXor()

        WordXor(0xFFFF0000, 0x00FFFFFF) = 0x000000FF
        HackersDelightXor(0x00000001, 0x00000001) = 0x00000000
        WordXor          (0x00000001, 0x00000001) = 0x00000001

        HackersDelightXor(0x00000001, 0x00000002) = 0x00000003
        WordXor          (0x00000001, 0x00000002) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000003) = 0x00000002
        WordXor          (0x00000001, 0x00000003) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000004) = 0x00000005
        WordXor          (0x00000001, 0x00000004) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000005) = 0x00000004
        WordXor          (0x00000001, 0x00000005) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000006) = 0x00000007
        WordXor          (0x00000001, 0x00000006) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000007) = 0x00000006
        WordXor          (0x00000001, 0x00000007) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000008) = 0x00000009
        WordXor          (0x00000001, 0x00000008) = 0x00000000

        HackersDelightXor(0x00000001, 0x00000009) = 0x00000008
        WordXor          (0x00000001, 0x00000009) = 0x00000000

        FAILURE: 4294934529 of 4294967296 tests failed

The measured failure of rate WordXor(), as a percentage, is 99.99923%.

Notice that the two nested loops in the Modula-2 test program run from
1 to MAXTEST; if they are changed to start at 0, this is what happens:

        % gm2 -g TestWordXor.mod && ./a.out
        Test of WordXor()

        WordXor(0xFFFF0000, 0x00FFFFFF) = 0x000000FF
        RTExceptions.mod:686:35: In wholediv
        RTExceptions.mod:686:35:illegal whole value exception
        Abort (core dumped)

A debugger traceback shows the call history:

        % gdb a.out
        (gdb) run
        ...
        Test of WordXor()

        WordXor(0xFFFF0000, 0x00FFFFFF) = 0x000000FF

        Thread 1 "a.out" received signal SIGFPE, Arithmetic exception.
        0x00007ffff79ca8c4 in m2log_BitWordOps_WordXor (left=0, right=0) at 
../../../../gcc-14-20240114/libgm2/libm2log/../../gcc/m2/gm2-libs-log/BitWordOps.mod:114
        114     
../../../../gcc-14-20240114/libgm2/libm2log/../../gcc/m2/gm2-libs-log/BitWordOps.mod:
 No such file or directory.
        (gdb) where
        #0  0x00007ffff79ca8c4 in m2log_BitWordOps_WordXor (left=0, right=0) at 
../../../../gcc-14-20240114/libgm2/libm2log/../../gcc/m2/gm2-libs-log/BitWordOps.mod:114
        #1  0x0000000000402677 in _M2_TestWordXor_init (argc=1, 
argv=0x7fffffffce88, envp=0x7fffffffce98) at TestWordXor.mod:49
        #2  0x00007ffff779e75c in m2pim_M2Dependent_ConstructModules 
(applicationmodule=<optimized out>, libname=<optimized out>, 
overrideliborder=<optimized out>, argc=1, argv=0x7fffffffce88, 
            envp=0x7fffffffce98) at 
../../../../gcc-14-20240114/libgm2/libm2pim/../../gcc/m2/gm2-libs/M2Dependent.mod:823
        #3  0x00000000004031d5 in _M2_init (argc=1, argv=0x7fffffffce88, 
envp=0x7fffffffce98) at TestWordXor.mod:1
        #4  0x000000000040323b in main (argc=1, argv=0x7fffffffce88, 
envp=0x7fffffffce98) at TestWordXor.mod:1

The Modula-2 code is several times slower than the C version.  That
gap could be narrowed if the bit operations were implemented via calls
to C functions that compile into hardware operations, instead of the
inefficient BITSET() implementation in BitWordOps.mod.

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                                                          -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe@math.utah.edu  -
- 155 S 1400 E RM 233                       beebe@acm.org  beebe@computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------