1#!/usr/bin/env python3
2#
3# Copyright 2016, Data61
4# Commonwealth Scientific and Industrial Research Organisation (CSIRO)
5# ABN 41 687 119 230.
6#
7# This software may be distributed and modified according to the terms of
8# the BSD 2-Clause license. Note that NO WARRANTY is provided.
9# See "LICENSE_BSD2.txt" for details.
10#
11# @TAG(D61_BSD)
12#
13
14# this script can be used to calculate the reciprocal for
15# unsigned division of an unknown 64 bit value by a known 64bit
16# constant. It is used to calculate the correct magic numbers
17# for fixed cpu times on arm in order to do 64 bit division to calculate
18# ticks -> microseconds.
19
20# for details on how this script works,
21# see Hacker's delight, Chapter 10, unsigned division.
22from math import floor, ceil
23import argparse
24import sys
25from past.builtins import xrange
26
27# now unsigned
28def magicgu(nmax, d):
29   nc = ((nmax + 1)//d)*d - 1
30   nbits = len(bin(nmax)) - 2
31   for p in range(0, 2*nbits + 1):
32      if 2**p > nc*(d - 1 - (2**p - 1)%d):
33         m = (2**p + d - 1 - (2**p - 1)%d)//d
34         return (m, p)
35   print("Can't find p, something is wrong.")
36   sys.exit(1)
37
38def do_div(n):
39    return ((n + add_ind) * magic) >> shift_amt
40
41if __name__ == "__main__":
42    parser = argparse.ArgumentParser(description="Generate magic numbers for emulating 64-bit division with multiplication by reciprocal using algorithm from Hacker's Delight, chapter 10.")
43    parser.add_argument("--divisor", type=int,required=True,help="Devisor to calculate magic numbers for")
44    args = parser.parse_args()
45
46    magic, shift_amt = magicgu(2**32 - 1, args.divisor)
47    print("magic number is: %d, shift amount is %d" % (magic, shift_amt))
48    add_ind = 0
49
50    print("Doing sanity check");
51    # sanity check
52    for i in xrange(2**32-1):
53        q1, q2 = (i / args.divisor, do_div(i))
54        if int(q1) != q2:
55            print("Combination failed %d %d %d" % i, q1, q2)
56            sys.exit(-1)
57
58    print("Success! Use (n * %d) >> %d to calculate n / %d" % (magic, shift_amt, args.divisor));
59    print("magic number is: %d, shift amount is %d" % (magic, shift_amt))
60