release/src-rt-6.x.4708/cfe/cfe/dev/popcount32.c

   1 /*
   2  * Misc utility routines for Hamming ecc calculation.
   3  *
   4  * Copyright (C) 2011, Broadcom Corporation. All Rights Reserved.
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  13  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  15  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  16  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  * ftp://ftp.be.netbsd.org/pub/NetBSD/NetBSD-release-6/src/common/lib/libc/string/popcount32.c
  19  * $Id:  $
  20  */
  21
  22 /*      $NetBSD: popcount32.c,v 1.4 2011/08/21 21:25:04 dholland Exp $  */
  23 /*
  24  * Copyright (c) 2009 The NetBSD Foundation, Inc.
  25  * All rights reserved.
  26  *
  27  * This code is derived from software contributed to The NetBSD Foundation
  28  * by Joerg Sonnenberger.
  29  *
  30  * Redistribution and use in source and binary forms, with or without
  31  * modification, are permitted provided that the following conditions
  32  * are met:
  33  *
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in
  38  *    the documentation and/or other materials provided with the
  39  *    distribution.
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  42  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  43  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  44  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  45  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  46  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  47  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  48  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  49  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  50  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  51  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  52  * SUCH DAMAGE.
  53  */
  54
  55
  56 /*
  57  * This a hybrid algorithm for bit counting between parallel counting and
  58  * using multiplication.  The idea is to sum up the bits in each Byte, so
  59  * that the final accumulation can be done with a single multiplication.
  60  * If the platform has a slow multiplication instruction, it can be replaced
  61  * by the commented out version below.
  62  */
  63
  64 #include <typedefs.h>
  65 unsigned int popcount32(uint32 v);
  66
  67 unsigned int
  68 popcount32(uint32 v)
  69 {
  70         unsigned int c;
  71
  72         v = v - ((v >> 1) & 0x55555555U);
  73         v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
  74         v = (v + (v >> 4)) & 0x0f0f0f0fU;
  75         c = (v * 0x01010101U) >> 24;
  76         /*
  77          * v = (v >> 16) + v;
  78          * v = (v >> 8) + v;
  79          * c = v & 255;
  80          */
  81
  82         return c;
  83 }
  84
  85 #if UINT_MAX == 0xffffffffU
  86 __strong_alias(popcount, popcount32)
  87 #endif
  88
  89 #if ULONG_MAX == 0xffffffffU
  90 __strong_alias(popcountl, popcount32)
  91 #endif