Re: Fast fixed division / remainder support

[Joerg Sonnenberger <joerg%britannica.bec.de@localhost>]

On Tue, Mar 16, 2010 at 03:35:52AM +0000, YAMAMOTO Takashi wrote:
> please use upper case names if they do something which can't be done
> if they were functions.  eg. assign results to some of args

I wasn't sure whether to use a macro or inline functions. Attached is a
full patch which goes with the latter.

Joerg

Index: bitops.h
===================================================================
RCS file: /home/joerg/repo/netbsd/src/sys/sys/bitops.h,v
retrieving revision 1.2
diff -u -p -r1.2 bitops.h
--- bitops.h    28 Apr 2008 20:24:10 -0000      1.2
+++ bitops.h    17 Mar 2010 22:06:33 -0000
@@ -1,11 +1,11 @@
 /*     $NetBSD: bitops.h,v 1.2 2008/04/28 20:24:10 martin Exp $        */
 
 /*-
- * Copyright (c) 2007 The NetBSD Foundation, Inc.
+ * Copyright (c) 2007, 2010 The NetBSD Foundation, Inc.
  * All rights reserved.
  *
  * This code is derived from software contributed to The NetBSD Foundation
- * by Christos Zoulas.
+ * by Christos Zoulas and Joerg Sonnenberger.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -256,4 +256,36 @@ fls64(uint64_t _n)
        -1) : ((sizeof(_n) >= 4 ? fls64(_n) : fls32(_n)) - 1) \
 )
 
+static inline void
+fast_divide32_prepare(uint32_t _div, uint32_t * __restrict _m,
+    uint8_t *__restrict _s1, uint8_t *__restrict _s2)
+{
+       uint64_t _mt;
+       int _l;
+
+       _l = (_div + 1 == 0) ? 32 : fls32(_div + 1);
+       _mt = 0x100000000ULL * ((1ULL << _l) - _div);
+       *_m = _mt / _div + 1;
+       *_s1 = (_l > 1) ? 1 : _l;
+       *_s2 = (_l == 0) ? 0 : _l - 1;
+}
+
+static inline uint32_t
+fast_divide32(uint32_t _v, uint32_t _div, uint32_t _m, uint8_t _s1,
+    uint8_t _s2)
+{
+       uint32_t _t;
+
+       _t = ((uint64_t)_v * _m) >> 32;
+       return (_t + ((_v - _t) >> _s1)) >> _s2;
+}
+
+static inline uint32_t
+fast_remainder32(uint32_t _v, uint32_t _div, uint32_t _m, uint8_t _s1,
+    uint8_t _s2)
+{
+
+       return _v - _div * fast_divide32(_v, _div, _m, _s1, _s2);
+}
+
 #endif /* _SYS_BITOPS_H_ */