correct • elegant • free

△ Comp.lang.c △

◅ function as parameter

Reading Date Stamp ▻

Expression to round up without branching

This is a micro-optimization question.  I am well aware of what the FAQ,
and several good books, say about micro-optimizations.  I am choosing to
waste my time on this one anyway: indulge me, or ignore me :-).

Consider this code fragment.

    #define ALIGN 16
    int n;

    /* Round n up to a multiple of ALIGN */
    n = ALIGN + n - (n % ALIGN);

The flaw is that if n is already a multiple of ALIGN, it increases it
to the next multiple.  For example, if n is initially 32, it becomes
48.  For my application, this is not a problem, but it does waste a tiny
amount of space.

I can easily eradicate the flaw, but at the cost of introducing a branch.

    n = (n % ALIGN) ? n : ALIGN + n - (n % ALIGN);

Is there a non-branching expression that achieves the same result?

You may assume that ALIGN will always be a power of 2.  (Indeed, the
original code I took this from used `n & (ALIGN - 1)' where I have
written `n % ALIGN'.  I have already confirmed that `gcc -O2' performs
the strength reduction and produces the same code for both versions.)

Tim Goodwin   | "If you don't know what closures are, you probably don't
Leicester, UK | want to know what closures are." -- Larry Wall

Original headers:

From: (Tim Goodwin)
Newsgroups: comp.lang.c
Subject: Expression to round up without branching
Date: 1 Feb 2000 16:46:07 -0000
Organization: A poorly-installed InterNetNews site
Message-ID: <8772l5$uko$>

△ Comp.lang.c △

◅ function as parameter

Reading Date Stamp ▻