1#!/usr/bin/env python3
2#
3# Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
4#
5# SPDX-License-Identifier: GPL-2.0-only
6#
7
8# this script can be used to calculate the reciprocal for
9# unsigned division of an unknown 64 bit value by a known 64bit
10# constant. It is used to calculate the correct magic numbers
11# for fixed cpu times on arm in order to do 64 bit division to calculate
12# ticks -> microseconds.
13
14# for details on how this script works,
15# see Hacker's delight, Chapter 10, unsigned division.
16from math import floor, ceil
17import argparse
18import sys
19from past.builtins import xrange
20
21# now unsigned
22
23
24def magicgu(nmax, d):
25    nc = ((nmax + 1)//d)*d - 1
26    nbits = len(bin(nmax)) - 2
27    for p in range(0, 2*nbits + 1):
28        if 2**p > nc*(d - 1 - (2**p - 1) % d):
29            m = (2**p + d - 1 - (2**p - 1) % d)//d
30            return (m, p)
31    print("Can't find p, something is wrong.")
32    sys.exit(1)
33
34
35def do_div(n):
36    return ((n + add_ind) * magic) >> shift_amt
37
38
39if __name__ == "__main__":
40    parser = argparse.ArgumentParser(
41        description="Generate magic numbers for emulating 64-bit division with multiplication by reciprocal using algorithm from Hacker's Delight, chapter 10.")
42    parser.add_argument("--divisor", type=int, required=True,
43                        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