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