summaryrefslogtreecommitdiffstats
path: root/pbn_ctz.c
blob: 07767ef8509f9545c6c3b3e2a9396c41178fcf47 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/* ----------------------------------------------------------------------- *
 *
 *   Copyright 2007 H. Peter Anvin - All Rights Reserved
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU Lesser General Public License as
 *   published by the Free Software Foundation, Inc.,
 *   59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
 *   incorporated herein by reference.
 *
 * ----------------------------------------------------------------------- */

/*
 * pbn_ctz.c
 */

#include <string.h>
#include <limits.h>
#include "pbnint.h"

static int pbn_limb_ctz(pbn_limb_t v)
{
    int p = PBN_LIMB_BITS;

#if defined(__GNUC__) && __GNUC__ >= 4
    if (sizeof(pbn_limb_t) == sizeof(int))
        return __builtin_ctz(v);
    if (sizeof(pbn_limb_t) == sizeof(long))
        return __builtin_ctzl(v);
    if (sizeof(pbn_limb_t) == sizeof(long long))
        return __builtin_ctzll(v);
    /* else fall through, wtf... */
#endif

#if PBN_LIMB_BITS > 32
    if (v & 0xffffffff)
	p -= 32;
    else
	v >>= 32;
#endif

    if (v & 0xffff)
	p -= 16;
    else
	v >>= 16;

    if (v & 0xff)
	p -= 8;
    else
	v >>= 8;

    if (v & 0xf)
	p -= 4;
    else
	v >>= 4;

    if (v & 0x3)
	p -= 2;
    else
	v >>= 2;

    if (v & 0x1)
	p -= 1;
    else
	v >>= 1;

    return p;
}

int pbn_ctz(const struct pbn *pbn)
{
    int n = 0;
    const pbn_limb_t *p = pbn->num;

    if (pbn->bits == 0)
        return -1;              /* Zero value */

    while (*p == 0) {
        p++;
        n += PBN_LIMB_BITS;
    }

    n += pbn_limb_ctz(*p);
    return n;
}