linux-mips
[Top] [All Lists]

Re: [PATCH 1/8] add lib/gcd.c

To: linux-kernel@vger.kernel.org
Subject: Re: [PATCH 1/8] add lib/gcd.c
From: James Cloos <cloos@jhcloos.com>
Date: Sat, 13 Jun 2009 08:16:04 -0400
Cc: "Linux-MIPS" <linux-mips@linux-mips.org>, Florian Fainelli <florian@openwrt.org>, Andrew Morton <akpm@linux-foundation.org>, Takashi Iwai <tiwai@suse.de>, Ralf Baechle <ralf@linux-mips.org>
Copyright: Copyright 2009 James Cloos
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jhcloos.com; s=eagle; t=1244895400; bh=NLT4aXezABQjRdsXnE4xz2bLu48geACnFL8WfrLXVxs=; h=From:To:Cc:Subject:In-Reply-To:References:Date:Message-ID: MIME-Version:Content-Type; b=JWF42XA4kdsatabc7haOY8lNTAY/LO/NrraYKGdu4BPYu1DuBRjY4g+OC2iTEwxaR 2Ogrln5Zv7OjX3NPqIg+srQhhpr/+LBiaEYv+obbdtj/mNk8nZYyUL/I9b4+Eyc//O 5tcxmaWPC4yHtJqai7ppHzTuqsdIbrUWrqIxdCto=
Face: iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAYAAAAf8/9hAAAABHNCSVQICAgIfAhkiAAAAI1J REFUOE+lU9ESgCAIg64P1y+ngUdxhl5H8wFbbM0OmUiEhKkCYaZThXCo6KE5sCbA1DDX3genvO4d eBQgEMaM5qy6uWk4SfBYfdu9jvBN9nSVDOKRtwb+I3epboOsOX5pZbJNsBJFvmQQ05YMfieIBnYX FK2N6dOawd97r/e8RjkTLzmMsiVgrAoEugtviCM3v2WzjgAAAABJRU5ErkJggg==
In-reply-to: <200906041615.10467.florian@openwrt.org> (Florian Fainelli's message of "Thu, 4 Jun 2009 16:15:07 +0200")
Openpgp: ED7DAEA6; url=http://jhcloos.com/public_key/0xED7DAEA6.asc
Openpgp-fingerprint: E9E9 F828 61A4 6EA9 0F2B 63E7 997A 9F17 ED7D AEA6
Original-recipient: rfc822;linux-mips@linux-mips.org
References: <200906041615.10467.florian@openwrt.org>
Sender: linux-mips-bounce@linux-mips.org
User-agent: Gnus/5.110011 (No Gnus v0.11) Emacs/23.0.92 (gnu/linux)
>>>>> "Florian" == Florian Fainelli <florian@openwrt.org> writes:

Florian> This patch adds lib/gcd.c which contains a greatest
Florian> common divider implementation taken from
Florian> sound/core/pcm_timer.c

Would the binary gcd algorithm not be a better fit for the kernel?

It avoids division, using only shifts and subtraction:

unsigned long gcd (unsigned long a, unsigned long b) {
        unsigned int shift;
        unsigned long d;
    
        if (a == 0 || b == 0)
                return a | b;
    
        for (shift = 0; ((a | b) & 1) == 0; ++shift) {
                a >>= 1;
                b >>= 1;
        }
    
        while ((a & 1) == 0)
                a >>= 1;
    
        do {
                while ((b & 1) == 0)
                        b >>= 1;
        
                if (a < b) {
                        b -= a;
                } else {
                        d = a - b;
                        a = b; b = d;
                }
                b >>= 1;
        } while (b != 0);
    
        return a << shift;
}

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

<Prev in Thread] Current Thread [Next in Thread>