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