5
\$\begingroup\$

Introduction

I was daunted by the complexity of Makefiles for even seemingly simple projects and I decided to rectify that. I also needed to make myself a few handy command-line tools for convenience (like when I don't have an internet connection). This project makes a utility program called gcd or gcd.exe on Windows. If you add it to PATH, you can use it anywhere.

The main GCD files

gcd.h

#ifndef GCD_H
#define GCD_H
#include <inttypes.h>

uint64_t gcd(const uint64_t a, const uint64_t b);

#endif

gcd.c

#include <inttypes.h>
#include "gcd.h"

uint64_t gcd(const uint64_t a, const uint64_t b)
{
    uint64_t p = a;
    uint64_t q = b;
    if (p == 0) { return q; }
    if (q == 0) { return p; }
    uint64_t r = p % q;
    while (r != 0) {
        p = q;
        q = r;
        r = p % q;
    }
    return q;
}

The Testing Apparatus

test.h

#ifndef TEST_H
#define TEST_H
#include <stdbool.h>

/*
 * Method to compare the equality of two integer expressions.
 * test : The name/description of the test being performed.
 * exp  : The expected value.
 * act  : The actual value. 
 */
bool check_uint64s_equal(const char * test, const uint64_t exp, const uint64_t act);

#endif

test.c

#include <stdio.h>
#include <stdbool.h>
#include <inttypes.h>

#include "test.h"

bool check_uint64s_equal(const char * test, const uint64_t exp, const uint64_t act)
{
    if (exp == act) {
        printf("PASSED: %s\n", test);
        return true;
    } else {
        printf("FAILED: %s\nExpected:\t%"PRIu64"\nActual:\t\t%"PRIu64"\n", test, exp, act);
        return false;
    }
}

gcd_tests.c

#include <stdio.h>
#include <stdlib.h>
#include "gcd.h"
#include "test.h"

/*
 * Unit Tests
 * ----------
 * 1. gcd(42, 56) = 14
 * 2. gcd(461952, 116298) = 18
 * 3. gcd(7966496, 314080416) = 32
 * 4. gcd(24826148, 45296490) = 526
 * 5. gcd(12, 0) = 12
 * 6. gcd(0, 0) = 0
 * 7. gcd(0, 9) = 9
 */

void test_gcd()
{
    int count = 0;
    int total = 0;
    ++total;
    count += check_uint64s_equal("gcd(42, 56) = 14",
            14, gcd(42, 56)) ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(461952, 116298) = 18",
            18, gcd(461952, 116298))  ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(7966496, 314080416) = 32",
            32, gcd(7966496, 314080416))  ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(24826148, 45296490) = 526",
            526, gcd(24826148, 45296490))  ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(12, 0) = 12",
            12, gcd(12, 0))  ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(0, 0) = 0",
            0, gcd(0, 0))  ? 1 : 0;
    ++total;
    count += check_uint64s_equal("gcd(0, 9) = 9",
            9, gcd(0, 9))  ? 1 : 0;

    printf("%d out of %d tests passed.\n", count, total);

    if (count != total) { exit(EXIT_FAILURE); }
}

int main(int argc, char const *argv[])
{
    test_gcd();
    return 0;
}

The Command Line Utility

#include <stdio.h>
#include <stdlib.h>
#include "gcd.h"

int main(int argc, char const *argv[])
{
    if (argc < 3) {
        printf("USAGE: gcd <int1> <int1> [<int3> ... <intn>]\n"
                "NOTE: Only positive integers are allowed.");
    }
    int index = 1;
    uint64_t divisor = 0;
    while (index < argc) {
        char const * arg = argv[index];
        long long value = strtoll(arg, NULL, 0);
        if (value < 0) {
            printf("Only positive integers please!\n");
            exit(EXIT_FAILURE);
        }
        divisor = gcd((uint64_t) value, divisor);
        index++;
    }
    printf("%"PRIu64"\n", divisor);
    return EXIT_SUCCESS;
}

The Makefile

.PHONY: all
all: util_gcd test_gcd

# This one makes the gcd utility: ./util/gcd or .\util\gcd.exe
util_gcd: util/gcd

util/gcd: obj/gcd.o obj/gcd_util.o
    gcc obj/gcd.o obj/gcd_util.o -o util/gcd

obj/gcd_util.o: src/gcd_util.c
    gcc -c src/gcd_util.c -o obj/gcd_util.o

# This one tests the code for GCD
test_gcd: bin/gcd_tests

bin/gcd_tests: obj/gcd.o obj/gcd_tests.o obj/test.o
    gcc obj/gcd.o obj/test.o obj/gcd_tests.o -o bin/gcd_tests

obj/gcd_tests.o: src/gcd_tests.c
    gcc -c src/gcd_tests.c -o obj/gcd_tests.o

obj/test.o: src/test.c src/test.h
    gcc -c src/test.c -o obj/test.o

obj/gcd.o: src/gcd.c src/gcd.h
    gcc -c src/gcd.c -o obj/gcd.o

.PHONY: clean
clean:
    rm ./obj/*.o
    rm ./bin/*

Usage

The tests can be run using .\bin\gcd_tests.exe or ./bin/gcd_tests and the following would be the result:

PASSED: gcd(42, 56) = 14
PASSED: gcd(461952, 116298) = 18
PASSED: gcd(7966496, 314080416) = 32
PASSED: gcd(24826148, 45296490) = 526
PASSED: gcd(12, 0) = 12
PASSED: gcd(0, 0) = 0
PASSED: gcd(0, 9) = 9
7 out of 7 tests passed.

Once added to path, the gcd utilty will work like this:

$ gcd 39 65
> 13
$ gcd 42 14 21
> 7

I would like comments on all aspects of the code, especially on the Makefile. It's my first attempt at something that's non-trivial and complicated to me, so I suppose there must be better ways of doing these.

\$\endgroup\$
  • 1
    \$\begingroup\$ long long value = strtoll(arg, NULL, 0); --> unsigned long long value = strtoull(arg, NULL, 0); \$\endgroup\$ – chux - Reinstate Monica Dec 21 '17 at 1:19
4
\$\begingroup\$
  • The dependencies of gcd.h and test.h are missing. If you modify them, the objects would not be rebuilt.

  • Stem rules let you avoid repetition:

    obj/%.o: src/%.c
        gcc -c $< -o $@
    

    is the (almost) only thing you need to generate all objects.

  • Almost, because you'd still need to add .h dependencies. gcc has a nice feature to autogenerate them:

    obj/%.d: src/%.c
        gcc -MM -MT $< -o $@
    

    will build the makefile fragments, which you need to include. And of course you don't want to list them all explicitly. make has a pattern substitution function. To set it up, define few macros:

    GCD_SOURCES := src/gcd.c src/gcd_util.c
    GCD_OBJECTS := $(patsubst src/%.c,obj/%.o,$(GCD_SOURCES))
    GCD_DEPS := $(patsubst src/%.c,obj/%.d,$(GCD_SOURCES))
    

    and similarly for TEST_SOURCES, and

    -include $(GCD_DEPS) $(TEST_DEPS)
    

    The GCD_OBJECTS is there to write the util/gcd rule:

    util/gcd: $(GCD_OBJECTS)
        gcc $^ -o util/gcd
    
  • The user of your distribution must manually create the obj, bin and util subdirectories. make can do it for you, with order-only prerequisite notation, for example

    util/gcd: $(GCD_OBJECTS) | util
        ....
    
    util:
        mkdir util
    
\$\endgroup\$
3
\$\begingroup\$

Nicely presented code - easy to read, clear in intent; nice one!

A few small improvements:

Interface

The const qualifiers to the prototype's formal parameters are meaningless here, and just add clutter. They are useful only in the definition of the function (but see below).

Implementation

Parameters a and b are passed by value, so there's no need to copy them into locals p and q. Make the parameters non-const, and allow the function to modify its copies.

Testing framework

I like to use a helper macro for assertion that can report both the expression passed to the test as well as its value. Something I've used for C++ is

template<typename A, typename B>
int verify(A aval, B bval, const char *a, const char *b,
           const char *file, int line)
{
    if (!(aval == bval))
        std::cerr << file << ":" << line << ": "
                  << a << " == " << b << "  --  "
                  << aval << " == " << bval << "\n";
    return !(aval == bval);
}

#define TEST_EQUAL(a, b) verify((a), (b), #a, #b, __FILE__, __LINE__)

The C equivalent would be something like (untested)

int verify_uint64(uint_64_t aval, uint_64_tB bval,
                  const char *a, const char *b,
                  const char *file, int line)
{
    if (aval != bval)
        fprintf(stderr, "%s:%d: %s (%" PRIu64") != %s (%" PRIu64")\n",
                file, line, a, aval, b, bval);
    return !(aval == bval);
}

#define TEST_EQUAL(a, b) verify((a), (b), #a, #b, __FILE__, __LINE__)

I use standard error stream for the failure messages, and keep quiet about the passes - on larger projects, you don't want the error messages drowned out by hundreds of lines of clutter. I've used a fairly conventional "File:Line:" format that's understood by tools such as Emacs's goto-error command.

Unlike the original, this version returns zero for success, and non-zero for failure. That makes it easy to determine overall success or failure without having to count the total number of tests, and it fits conveniently with return conventions from main() - we can just add the total number of failures, and return that:

int main()
{
    return TEST_EQUAL(gcd(0, 0), 0)
        +  TEST_EQUAL(gcd(1, 0), 1)
        +  TEST_EQUAL(gcd(0, 1), 1)
        +  TEST_EQUAL(gcd(42, 56), 14)
        // etc.
        ;
}

Test cases

Remember to test the boundaries of acceptable input - I'd like to see tests for each combination of 0, 1, UINT64_MAX, as well as an obviously co-prime pair - 2, 3 is the obvious first example. We also need a test where a==b.

Utility program

Prefer to use the standard error stream for error messages, and standard output only for normal output. This makes it easier to combine your program with others, by pipelines or command substitution.

We could simply return EXIT_FAILURE; rather than exit(EXIT_FAILURE); - that would make it consistent with the success path.

The Makefile

I'll assume that you always use GNU Make - it's generally easier to install this where you need it than to write a truly portable Makefile.

Make works best if the Makefile is invoked where the outputs will be created; you can use the VPATH mechanism to locate the sources. The Makefile could still live with your sources, if you then use make -f to locate it.

Instead of insisting on gcc as compiler, you should allow the user to specify CC and CFLAGS in the usual way. If you follow the advice to use VPATH, you won't even need to write any rules for the object files; otherwise, a single pattern rule shows how to create the object files:

obj/%.o: src/%.c
    $(COMPILE.c) $(OUTPUT_OPTION) $^

# Additional dependencies - TODO: auto-generate these
obj/gcd.o: src/gcd.h
obj/test.o: src/test.h
# These ones were missing - that's why we should auto-generate!
obj/gcd_tests.o: src/gcd.h
obj/gcd_tests.o: src/test.h
obj/gcd_util.o: src/gcd.h

Similarly, you can use the $(LINK.c) predefined variable to combine the object files, respecting $(LDFLAGS). If you forget what the built-in rules are, remember that you can inspect the output of make -f /dev/null --print-data-base.

It's a good idea to create a target that actually runs the tests. I like to create a results file, so as to re-run the tests only when the code has changed, but if you want the rule to always run the tests, then you can make it a phony target. If you're feeling strict, you could make the linking of the final utility depend on the run-tests target, so you don't build a program you know won't work.

You might also have a target that runs the tests using Valgrind - either as a target in itself, or by providing a TEST_TOOL variable, like this:

tests.log: test_gcd
    $(TEST_TOOL) $< 2>&1 | tee $@
\$\endgroup\$
1
\$\begingroup\$

Detecting negative textual input.

    long long value = strtoll(arg, NULL, 0);
    if (value < 0) {
        printf("Only positive integers please!\n");
        exit(EXIT_FAILURE);
    }

This is a bit tricky for unsigned types. Using strtoll(arg, NULL, 0) as OP did, loses the full range of uint64_t as that returns LLONG_MAX for greater textual values like "0x8000000000000000".

strtoull(), being generous, will gladly convert input like "-1" to ULLONG_MAX or "-0xFFFFFFFF" to 1 with no error. The '-' is applied after the numeric conversion to the unsigned value and "wraps-around".

A solution, if full 64-bit range is desired: use both or search for '-'. Additional code below checks for no conversion arg == endptr, extra text *endptr, and out of range conversion errno.

    char *endptr;
    errno = 0;
    unsigned long long value = strtoull(arg, &endptr, 0);
    if (arg == endptr || *endptr || errno || strchr(arg, "-")
        // Further growth where long long may be > 64 bit
        #if ULLONG_MAX > UINT64_MAX
          || (value > UINT64_MAX)
        #endif
        ) {
      printf("Only positive 64-bit integers please!\n");
      exit(EXIT_FAILURE);
    }

    divisor = gcd((uint64_t) value, divisor);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.