Incorrect result for unsigned divide with branchfree mode when divisor == 1

[otherjason]

Self-contained example:

#include "libdivide.h"
#include <iostream>

int main()
{
    {
        libdivide::divider<uint32_t, libdivide::BRANCHFREE> du(1);
        std::cout << "u32 result branchfree: " << (1U / du) << std::endl;

        libdivide::divider<uint32_t> du2(1);
        std::cout << "u32 result branchful: " << (1U / du2) << std::endl;
    }
    {
        libdivide::divider<uint64_t, libdivide::BRANCHFREE> du(1);
        std::cout << "u64 result branchfree: " << (1UL / du) << std::endl;

        libdivide::divider<uint64_t> du2(1);
        std::cout << "u64 result branchful: " << (1UL / du2) << std::endl;
    }

    {
        libdivide::divider<int32_t, libdivide::BRANCHFREE> du(1);
        std::cout << "s32 result branchfree: " << (1 / du) << std::endl;

        libdivide::divider<int32_t> du2(1);
        std::cout << "s32 result branchful: " << (1 / du2) << std::endl;
    }
    {
        libdivide::divider<int64_t, libdivide::BRANCHFREE> du(1);
        std::cout << "u64 result branchfree: " << (1L / du) << std::endl;

        libdivide::divider<int64_t> du2(1);
        std::cout << "u64 result branchful: " << (1L / du2) << std::endl;
    }
}

This should calculate 1 / 1, which should be 1. However, this program prints:

u32 result branchfree: 0
u32 result branchful: 1
u64 result branchfree: 0
u64 result branchful: 1
s32 result branchfree: 1
s32 result branchful: 1
u64 result branchfree: 1
u64 result branchful: 1

This was compiled on Ubuntu 16.04 with:

g++ (Ubuntu 5.4.0-6ubuntu1~16.04.1) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I see the same behavior with -O0 or -O3.

[kimwalisch]

This should calculate 1 / 1, which should be 1. However, this program prints:

Unfortunately this is by design, we even have assertions in the code that check this case:

static inline struct libdivide_u32_t libdivide_internal_u32_gen(uint32_t d, int branchfree) {
    // 1 is not supported with branchfree algorithm
    LIBDIVIDE_ASSERT(!branchfree || d != 1);

static inline struct libdivide_u64_t libdivide_internal_u64_gen(uint64_t d, int branchfree) {
    // 1 is not supported with branchfree algorithm
    LIBDIVIDE_ASSERT(!branchfree || d != 1);

The branchfree algorithm works for all integers except for 1 (and 0 obviously). We could probably make it work for 1 as well by adding a bunch of nasty operations but this would most likely slow down the algorithm so much that it would be totally useless.

The branchfree algorithm is very new, so it has not yet been documented yet on http://libdivide.com/documentation.html. To me the branchfree algorithm is still very usefull as is, I am using it in my primecount project and it gives me a nice speed up compared to the default branchfull algorithm.

[otherjason]

I see; that makes sense. I'm surprised that the assertions didn't fire, but it's not a huge deal for me. In my use case, I would never be dividing by 1 anyway.

[kimwalisch]

The assertion did not fire because by default assertions are disabled in libdivde (for performance reasons).