K&R C Programs Exercise 7-9

Exercise 7-9. Functions like isupper can be implemented to save space or to save time. Explore both possibilities.

Standard library character-classification functions like isupper are typically implemented as macros. There are two design axes:

• Save time: use a precomputed lookup table — one array access, no branches, O(1) at maximum cache efficiency
• Save space: use an expression — no table needed, just a comparison or two

This exercise explores both, then extends them to all classification functions in <ctype.h>.

Solution

/* K&R Exercise 7-9 — isupper and friends: space-saving vs time-saving
 * Compile: gcc -ansi -Wall ex7-9.c -o ex7-9 */
#include <stdio.h>

/* ---- save-space versions: pure expressions, no tables ---- */

/* Works for ASCII (A=65 Z=90, a=97 z=122, 0=48 9=57) */
#define SS_isupper(c)  ((c) >= 'A' && (c) <= 'Z')
#define SS_islower(c)  ((c) >= 'a' && (c) <= 'z')
#define SS_isdigit(c)  ((c) >= '0' && (c) <= '9')
#define SS_isalpha(c)  (SS_isupper(c) || SS_islower(c))
#define SS_isalnum(c)  (SS_isalpha(c) || SS_isdigit(c))
#define SS_isspace(c)  ((c)==' ' || (c)=='\t' || (c)=='\n' || \
                        (c)=='\r' || (c)=='\f' || (c)=='\v')
#define SS_toupper(c)  (SS_islower(c) ? (c) - ('a' - 'A') : (c))
#define SS_tolower(c)  (SS_isupper(c) ? (c) + ('a' - 'A') : (c))

/* ---- save-time versions: bitfield lookup table ---- */

/* Each entry is a bitmask of which classes the character belongs to */
#define F_UPPER  0x01
#define F_LOWER  0x02
#define F_DIGIT  0x04
#define F_SPACE  0x08

static unsigned char _ct[256];

static void init_ctype_table(void)
{
    int c;
    for (c = 'A'; c <= 'Z'; c++) _ct[(unsigned char)c] |= F_UPPER;
    for (c = 'a'; c <= 'z'; c++) _ct[(unsigned char)c] |= F_LOWER;
    for (c = '0'; c <= '9'; c++) _ct[(unsigned char)c] |= F_DIGIT;
    _ct[(unsigned char)' ']  |= F_SPACE;
    _ct[(unsigned char)'\t'] |= F_SPACE;
    _ct[(unsigned char)'\n'] |= F_SPACE;
    _ct[(unsigned char)'\r'] |= F_SPACE;
    _ct[(unsigned char)'\f'] |= F_SPACE;
    _ct[(unsigned char)'\v'] |= F_SPACE;
}

#define ST_isupper(c)  (_ct[(unsigned char)(c)] & F_UPPER)
#define ST_islower(c)  (_ct[(unsigned char)(c)] & F_LOWER)
#define ST_isdigit(c)  (_ct[(unsigned char)(c)] & F_DIGIT)
#define ST_isalpha(c)  (_ct[(unsigned char)(c)] & (F_UPPER|F_LOWER))
#define ST_isalnum(c)  (_ct[(unsigned char)(c)] & (F_UPPER|F_LOWER|F_DIGIT))
#define ST_isspace(c)  (_ct[(unsigned char)(c)] & F_SPACE)

/* ---- test harness ---- */

static void test(int c)
{
    /* Compare save-space vs save-time results */
    int ss_up = SS_isupper(c), st_up = ST_isupper(c) != 0;
    int ss_lo = SS_islower(c), st_lo = ST_islower(c) != 0;
    int ss_di = SS_isdigit(c), st_di = ST_isdigit(c) != 0;
    int ss_sp = SS_isspace(c), st_sp = ST_isspace(c) != 0;

    if (ss_up != st_up || ss_lo != st_lo || ss_di != st_di || ss_sp != st_sp) {
        printf("MISMATCH at c=%d ('%c')\n", c, c);
    }
}

int main(void)
{
    int c;
    init_ctype_table();

    /* Verify: SS and ST agree on all 128 ASCII characters */
    for (c = 0; c < 128; c++)
        test(c);
    printf("All SS/ST results agree for ASCII 0-127\n\n");

    /* Demonstrate save-space macros */
    printf("Save-space macros:\n");
    printf("  isupper('A')=%d  islower('a')=%d  isdigit('5')=%d\n",
           SS_isupper('A'), SS_islower('a'), SS_isdigit('5'));
    printf("  toupper('g')='%c'  tolower('G')='%c'\n",
           SS_toupper('g'), SS_tolower('G'));

    /* Demonstrate save-time macros */
    printf("\nSave-time macros (table lookup):\n");
    printf("  isupper('Z')=%d  isspace('\\t')=%d  isalnum('3')=%d\n",
           ST_isupper('Z') != 0, ST_isspace('\t') != 0, ST_isalnum('3') != 0);

    /* Show trade-offs */
    printf("\nSpace used by table: %zu bytes\n", sizeof(_ct));
    printf("Space used by SS macros: 0 bytes of data (code only)\n");
    return 0;
}

Compile and Run

gcc -ansi -Wall ex7-9.c -o ex7-9
./ex7-9

Expected Output

All SS/ST results agree for ASCII 0-127

Save-space macros:
  isupper('A')=1  islower('a')=1  isdigit('5')=1
  toupper('g')='G'  tolower('G')='g'

Save-time macros (table lookup):
  isupper('Z')=1  isspace('\t')=1  isalnum('3')=1

Space used by table: 256 bytes
Space used by SS macros: 0 bytes of data (code only)

Trade-off Summary

What This Exercise Teaches

• Bitfield tables — storing multiple boolean properties per character in a single byte's bits is the standard technique used by real ctype.h implementations; each classification is a single bitwise AND
• Expression macros vs table macros — expression macros compile to a handful of instructions and use no heap/BSS memory; table macros use 256 bytes of BSS but reduce instruction count to one load + one AND
• (unsigned char) cast — essential when indexing into the table with a potentially signed char; on systems where char is signed, values above 127 would be negative and index out of bounds

Set Up Your C Environment

• Install GCC on Windows
• Install GCC on Linux
• Install GCC on macOS
• VS Code for C

← Exercise 7-8  | 
Chapter 7 Solutions

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie