Exercise 1

From CS260r 2015
Jump to: navigation, search

To appreciate the subtleties of correct coding and complete testing, let’s start with a deceptively simple exercise borrowed from the amazing John Regehr.

Saturating arithmetic operations are those where overflowing results “stick” at the maximum or minimum representable result. In other words, if you are using saturating addition and subtraction operators, INT_MAX + 1 == INT_MAX and INT_MIN - 1 == INT_MIN. Here are the prototypes for four saturating arithmetic operations that you must implement; save these prototypes to a file called sat_ops.h:

#ifndef ARITHTYPE
// define this to a number between 0 and 4
#define ARITHTYPE 2
#endif

#if ARITHTYPE == 0
typedef signed char mysint;
typedef unsigned char myuint;
#elif ARITHTYPE == 1
typedef short mysint;
typedef unsigned short myuint;
#elif ARITHTYPE == 2
typedef int mysint;
typedef unsigned int myuint;
#elif ARITHTYPE == 3
typedef long mysint;
typedef unsigned long myuint;
#elif ARITHTYPE == 4
typedef long long mysint;
typedef unsigned long long myuint;
#else
#error "Unknown ARITHTYPE"
#endif

/** Return the value of @x + @y using saturating unsigned addition. */
myuint sat_unsigned_add(myuint x, myuint y);

/** Return the value of @x - @y using saturating unsigned subtraction. */
myuint sat_unsigned_sub(myuint x, myuint y);

/** Return the value of @x + @y using saturating signed addition. */
mysint sat_signed_add(mysint x, mysint y);

/** Return the value of @x - @y using saturating signed subtraction. */
mysint sat_signed_sub(mysint x, mysint y);

Your functions should live in a file called sat_ops.c that you create. Some other requirements:

  • Your code must compile without warnings using both Clang and GCC for x86-64. For GCC and Clang, make sure you use the -Wall option to enable extra warnings.
  • You must write C or C++, no assembly language.
  • Your code must not execute any math operations with undefined behavior, such as shift past bitwidth or signed overflow. Recent C compilers, such as gcc-4.9 (available via Homebrew as gcc49) and llvm-3.7, offer an -fsanitize=undefined option that can help you test. For example, running this program:
    #include <limits.h>
    int __attribute__((noinline)) f(void) {
        return INT_MAX;
    }
    int main(void) {
        return f() + 1;
    }
    

    as compiled by gcc-4.9 -fsanitize=undefined x.c, produces this result:

    x.c:6:5: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
    
    The code you hand in must not produce any of these errors.
  • You may use the C preprocessor to write macros and to include files, but you must not use conditional compilation—your code cannot branch on the value of ARITHTYPE. If you choose to write macros and your macros are incorrect, points will be deducted.
  • Your code must be independent of the bitwidth of the operations. In other words, the same exact C code must correctly implement the saturating operations no matter which of the typedefs at the top of sat_ops.h is enabled.
  • You will not receive credit for incorrect code. In other words, test your code before handing it in. Be creative and try to test different combinations of values that exercise various corner cases in your code.
  • The file you handin should not include a main function.
  • Do not put the text of sat_ops.h into your C file! rather, include it using the #include directive.
  • Big hint: You do not get a correct sat_signed_sub by implementing it as sat_signed_add(a, -b). I won't explain this further, it's not hard to work out the reason on your own.

A special prize may be given to the student whose correct code, when compiled with gcc-4.9’s -Os option, and with 32-bit ints (ARITHTYPE==2), has the smallest size in bytes.