1. Introduction

kmul is a generator of routines for optimized multiplication by an integer constant. In order to calculate a constant integer multiplication, it uses the public domain routines presented in the work: Preston Briggs and Tim Harvey, "Multiplication by integer constants," Technical report, Rice University, July 1994. This technical report implements Bernstein's algorithm documented in: R. Bernstein, "Multiplication by integer constants," Software - Practice and Experience, Vol. 16, No. 7, pp. 641-652, July 1986.

kmul can also be used for emitting a NAC (generic assembly language) or ANSI C implementation of the multiplication.

2. File listing

The kmul distribution includes the following files:

3. Installation

There exists a quite portable Makefile (Makefile in the current directory). Running make from the command prompt should compile kmul.

4. Prerequisites

• [mandatory for building] Standard UNIX-based tools
• gcc (tested with gcc-3.4.4 on cygwin/x86)
• make
• bash

5. kmul usage

The kmul program can be invoked with several options (see complete option listing below). The usual tasks that can be accomplished with kmul are:

• generate a NAC optimized software routine for the multiplication
• generate an ANSI C optimized software routine for the multiplication.

ANSI C routines are emitted only for a width of 32-bits (see option below).

kmul can be invoked as:

The complete kmul options listing:

-h

Print this help.

-d

Enable debug/diagnostic output.

-mul <num>

Set the value of the multiplier. Default: 1.

-width <num>

Set the bitwidth of all operands: multiplier, multiplicand and product. Default: 32.

-signed

Construct optimized routine for signed multiplication.

-unsigned

Construct optimized routine for unsigned multiplication (default).

-nac

Emit software routine in the NAC general assembly language (default).

-ansic

Emit software routine in ANSI C (only for width=32).

Here follow some simple usage examples of kmul.

1. Generate the ANSI C implementation of n*11 optimized routine.

2. Generate the NAC implementation of n*(-7) optimized routine.

3. Generate the ANSI C implementation of n*23 optimized routine with debugging output.

6. Quick tutorial

kmul can be used for arithmetic optimizations in user programs. Assume the following user program (test.c):

// test.c
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  int a, b;
  a = atoi(argv[1]);
  b = a * 23;
  printf("b = %d\n", b);
  return b;
}

This file is compiled and run as follows with one additional argument:

and the expected result is:

The user can apply kmul for generating a constant multiplication routine for a*23:

and the corresponding routine is produced (local variables t5 to t15 can be deleted by the user; the compiler will be optimize them away eventually). Then, the user should edit a new file, let's say test.opt.c and include the produced routine. The resulting optimized source file should be as follows:

// test.opt.c
#include <stdio.h>
#include <stdlib.h>
signed int kmul_s32_p_23 (signed int x)
{
  signed int t0;
  signed int t1;
  signed int t2;
  signed int t3;
  signed int t4;
  signed int t5;
  signed int t6;
  signed int t7;
  signed int t8;
  signed int t9;
  signed int t10;
  signed int t11;
  signed int t12;
  signed int t13;
  signed int t14;
  signed int t15;
  signed int y;
  t0 = x;
  t1 = t0 << 1;
  t2 = t1 + x;
  t3 = t2 << 3;
  t4 = t3 - x;
  y = t4;
  return (y);
}

int main(int argc, char *argv[]) {
  int a, b;
  a = atoi(argv[1]);
  b = kmul_s32_p_23(a);
  printf("b = %d\n", b);
  return b;
}

This file is compiled and run as follows with one additional argument:

The target platform compiler (e.g. gcc or llvm) is expected to inline the kmul_s32_p_23 function at its call site.

7. Running tests

In order to build and run a series of sample tests do the following:

or for a more extensive set of tests:

8. Contact

You may contact me for further questions/suggestions/corrections at: