Division by a constant

Hi Rob and Glen

have you used kdiv, my constant division routine generator?

It produces low-level ("assembly") and C implementations for constant division.

http://github.com/nkkav/kdiv

Many people are happy with it; it is based on Warren's Hackers' Delight.

Best regards,
Nikolaos Kavvadias
http://www.nkavvadias.com



> 
> (snip, I wrote)
> >> With the multiply instruction on many processors, that generates a
> >> double length signed product, I believe that for many constants,
> >> maybe half of them, there is a multiplier that will generate the
> >> appropriate truncated quotient in the high half of the product.
>  
> > Right, and I've never seen a multiplier block in an FPGA that 
> > doesn't do the same.  For a while they were 18x18=>36, then 
> > I started hitting 18*25=>43, but regardless, the hard 
> > multiplier blocks always generate 
> > P'length = A'length + B'length.
>  
> >> But in the case the OP asked, it isn't so obvious that it should do
> >> that.
>  
> >> Another choice would be a primitive that would generate the appropriate
> >> multiplier.
>  
> > Ugh, but then you'd have to instantiate it as a separate block and wire 
> > it in.  That's even uglier than having to put the bit-shifting logic in 
> > manually.
> 
> Yes it is ugh, but you know that you are asking for one. 
>  
> >> Often when you want a divider, you want it pipelined, 
> >> which is unlikely to be synthesized.
>  
> > Not really.  Often when I want a divider I have to pipeline it because 
> > the division algorithm is inherently serial.  But I don't _want_ it to be 
> > pipelined, that's just the only choice I've got for a true X/Y divide.
> 
> Well, I usually go the FPGA route when I want something done fast,
> which means pipelined. Maybe not everyone does that.
>  
> > But for X/K with constant K, it can (in every case I've seen) be 
> > implemented with a multiplier block, or simply by wire if K is 
> > a power of 2.  That gets us done in a single cycle.
>  
> > Sure that multiplier block may blow up into horrible cross-multiplies 
> > spanning multiple blocks if I ask for a stupidly large K.  But the same 
> > can be said for X*K, and the tool lets me request that just fine, and if 
> > I ask for a stupid K I get a mess of logic that either a) only meets 
> > timing with a slow clock or b) requires me to make a few stages of 
> > register pushback available.
> 
> For software, you usually have (N)*(N)=(2N) and (2N)/(N)=(N)
> 
> In the FPGA case, even though the hardware is 18 bits, you can
> choose any number of bits for your actual values. 
> 
> I am pretty sure that if you have one more bit in the constant
> than you need in the quotient, that it is enough. I am not sure
> that it always is when you have the same number of bits.
> 
> That is, I am not sure that you can generate a 32 bit signed 
> quotient as the high half of a 32 bit multiply for all possible 32
> bit signed divisors. 
> 
> -- glen