[PATCH v2.0] Use saturated arithmetic for overflow detection.

[Ondřej Bílka]

On Sun, Nov 03, 2013 at 01:20:14AM -0700, Paul Eggert wrote:
> Ondřej Bílka wrote:
> > checking takes 10 bytes for branch version, 12 bytes in branchfree
> > version.
> 
> When I try it, the branch version takes one byte more than
> the branchfree version.  This is when I do branching (or branchfree)
> for both adding and multiplying.  Here's the testcase.  Compiled
> with -O3, foo_branch is 32 bytes and foo_branchfree 31.
>
I was referring to version with a sbb trick to decrease size which I
mentioned but did not send new version.

This also improves code size a bit because for addition we do not
require specific registers.
For multiplication we must use rdx:rax pair due to instruction
semantics.


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

static inline size_t
add_sat_branch (size_t x, size_t y)
{
  size_t ret;
  asm ("add %2, %0; jnc 1f; sbb %0, %0;  1:" : "=r" (ret) : "0" (x) , "r" (y));
  return ret;
}

static inline size_t
add_sat_branchfree (size_t x, size_t y)
{
  size_t ret, scratch;
  asm ("add %1, %0; sbb %1, %1; or %1, %0" : "=r" (ret), "=r" (scratch) : "0" (x) , "1" (y));
  return ret;
}

static inline size_t
mul_sat_branch (size_t x, size_t y)
{
  size_t ret, scratch;
  asm ("mul %%rdx; jno 1f; sbb %%rax, %%rax;  1:" : "=a" (ret), "=d" (scratch) : "a" (x) , "d" (y));
  return ret;
}

static inline size_t
mul_sat_branchfree (size_t x, size_t y)
{
  size_t ret;
  size_t scratch;
  asm ("mul %%rdx; sbb %%rdx, %%rdx; or %%rdx, %%rax" : "=a" (ret), "=d" (scratch) : "a" (x) , "d" (y));
  return ret;
}

size_t
foo_branch (size_t a)
{
  return add_sat_branch (mul_sat_branch (a, 42 * 3), 8);
}

size_t
foo_branchfree (size_t a)
{
  return add_sat_branchfree (mul_sat_branchfree (a, 42 * 3), 8);
}