From owner-freebsd-arch@freebsd.org Tue Jan 8 07:46:09 2019 Return-Path: Delivered-To: freebsd-arch@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id E11081492E03 for ; Tue, 8 Jan 2019 07:46:08 +0000 (UTC) (envelope-from gavin.d.howard@gmail.com) Received: from mail-vs1-xe41.google.com (mail-vs1-xe41.google.com [IPv6:2607:f8b0:4864:20::e41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id BBE40734E2; Tue, 8 Jan 2019 07:46:07 +0000 (UTC) (envelope-from gavin.d.howard@gmail.com) Received: by mail-vs1-xe41.google.com with SMTP id y27so1917760vsi.1; Mon, 07 Jan 2019 23:46:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=zIU2qWvNz3Li8iVCmed/uynXGeJm5Qmt2Oaf+p34PL0=; b=pB1qgIPW/VnnCTt80t1qBaJtj94GTiSNcwiPUF3p6+XnAMj1wr9hlrnOcwyujbkA2E au5Ihu/+q5lb4lMCg+wzURE4+jh6rcPpzrpkvOlAO6h5a13zTpLsHC3sSTg1GPt5qqYZ BVJXb9GPfq7EN+NlCXKOd+ZySvn94Rtl2mzxTigBhLhKqWxu7SZBqDL+nRE5CKalTyOR UeVDsaJndsvoFS2wK3iomD18A+i0bkIGb1RwYHLhKuZmILmCu4XJxypWcps/Vrp7CleU p8JbA7uFN39ef47h8jgW4i1idlrMc2oPSJeWWo5r7KHI0i/gYnLzRCAm0/5KCUvxCAYr vwXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=zIU2qWvNz3Li8iVCmed/uynXGeJm5Qmt2Oaf+p34PL0=; b=Y7yApt1yfikI8GvAA1bfeYg4j93GxQkDEAtQgvPUbHDFuM6hIq1ldyqAccp8EoOclE fp5sXAsxw7kNtnyYSiMY3sb09AhpwII04bte/MPPcls0lAE3Ktf1fAIFLMdLS9UdfLiB gRg95XAZBwRAfhpxF+W1uT4ngMQtc2/p3AAzScKpmO90GN77f36wXtwz+/4rmD41qsap fGb6wtsuqoMirunWJ+5fnrM8aDE//Ws347yh1I4jz/zOzLeLZVufs9h9XalE6E6xs9+5 UYNPQ0VSEDt4re2qP/5tp7ye0S6+0tykqnEHrOVcl11vJe2uO2o4Lx/HHI9xZkspXg7j wVnA== X-Gm-Message-State: AJcUuketeHxvguKS76dRqjLZqvYRUDPDpjPRhHaxPx57RReP2XfjAOMI bggiqdDWy8xDfTDxKAy6y7BYzz/ds+KyPqhvFMR2HrZv X-Google-Smtp-Source: ALg8bN5mfWbiY7eDW3dZ5XdtX+si8vK4i9joFyXolmlJlAHX1Wr7NJVWdPWVvqZ34R+cIeVFcRPCJwU1zaJgO6Q74i8= X-Received: by 2002:a67:fa59:: with SMTP id j25mr304544vsq.18.1546933566868; Mon, 07 Jan 2019 23:46:06 -0800 (PST) MIME-Version: 1.0 References: <8FFA4578-0BAE-4F9F-8A06-AE83283BDEA4@FreeBSD.org> <61F802DC-2E59-4E0A-955D-899EBD7874A1@FreeBSD.org> In-Reply-To: <61F802DC-2E59-4E0A-955D-899EBD7874A1@FreeBSD.org> From: Gavin Howard Date: Tue, 8 Jan 2019 00:45:30 -0700 Message-ID: Subject: Re: GNU-compatible, BSD-licensed bc To: Devin Teske Cc: cem@freebsd.org, "freebsd-arch@freebsd.org" Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: BBE40734E2 X-Spamd-Bar: - Authentication-Results: mx1.freebsd.org; dkim=pass header.d=gmail.com header.s=20161025 header.b=pB1qgIPW; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (mx1.freebsd.org: domain of gavindhoward@gmail.com designates 2607:f8b0:4864:20::e41 as permitted sender) smtp.mailfrom=gavindhoward@gmail.com X-Spamd-Result: default: False [-1.37 / 15.00]; TO_DN_EQ_ADDR_SOME(0.00)[]; TO_DN_SOME(0.00)[]; R_SPF_ALLOW(-0.20)[+ip6:2607:f8b0:4000::/36]; FREEMAIL_FROM(0.00)[gmail.com]; DKIM_TRACE(0.00)[gmail.com:+]; DMARC_POLICY_ALLOW(-0.50)[gmail.com,none]; MX_GOOD(-0.01)[cached: alt3.gmail-smtp-in.l.google.com]; FROM_EQ_ENVFROM(0.00)[]; RCVD_TLS_LAST(0.00)[]; MIME_TRACE(0.00)[0:+]; FREEMAIL_ENVFROM(0.00)[gmail.com]; ASN(0.00)[asn:15169, ipnet:2607:f8b0::/32, country:US]; TAGGED_FROM(0.00)[]; DWL_DNSWL_NONE(0.00)[gmail.com.dwl.dnswl.org : 127.0.5.0]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-0.59)[-0.588,0]; R_DKIM_ALLOW(-0.20)[gmail.com:s=20161025]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_HAM_LONG(-0.63)[-0.627,0]; MIME_GOOD(-0.10)[text/plain]; IP_SCORE(0.26)[ip: (5.26), ipnet: 2607:f8b0::/32(-2.21), asn: 15169(-1.68), country: US(-0.08)]; NEURAL_SPAM_SHORT(0.60)[0.601,0]; RCVD_IN_DNSWL_NONE(0.00)[1.4.e.0.0.0.0.0.0.0.0.0.0.0.0.0.0.2.0.0.4.6.8.4.0.b.8.f.7.0.6.2.list.dnswl.org : 127.0.5.0]; RCVD_COUNT_TWO(0.00)[2] X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 08 Jan 2019 07:46:09 -0000 On Mon, Jan 7, 2019 at 10:57 PM Devin Teske wrote: > > > > > On Jan 7, 2019, at 4:42 PM, Gavin Howard wrote: > > > > On Mon, Jan 7, 2019 at 5:38 PM Conrad Meyer wrote: > >> > >> On Mon, Jan 7, 2019 at 4:00 PM Devin Teske wrote: > >>> How do you handle arbitrary arithmetic precision? > >> > >> Looks like https://github.com/gavinhoward/bc/blob/master/src/num.c . > > > > That is correct. Because this bc is meant to help bootstrap the Linux > > kernel and have no dependencies other than POSIX 2008, I wrote my own. > > Impressive. It might be worth turning this into a library itself. Eh...it is completely tuned for bc. And it won't be fast, unfortunately. See below. > > Also, the POSIX bc standard mandates doing math in decimal. OpenSSL > > would not be smart if they did that. > > Not sure I understand what you mean here. Well, for starters, OpenSSL's BIGNUM is integer only. Yes, those integers can be any size, but they are only integers. That is not good enough for bc; it has to allow arbitrary precision, including non-integers, and its fractional part can be any size, up to a certain limit, which you can get from my bc by typing "limits" at the prompt and looking for the value of BC_NUM_MAX (which is actually the maximum number of decimal digits, period). Also, while bc requires arithmetic to be in decimal, OpenSSL probably uses unsigned integers to do binary-based arithmetic. Let me explain. (And yes, I am explaining in detail, even though you probably know this already. I am just making sure I cover my bases.) In any (normal) bignum implementation, a bignum is going to be an array of hardware-based integers (in the case of OpenSSL, probably unsigned ints). A normal bignum implementation would use the entire range (or almost the entire range) of that integer type. For 32-bit unsigned integers, that means that each "limb" (item in the bignum array) can hold 2^32 integers. For a hardware-based, unsigned integer implementation, that means that it only needs one item in the array until the bignum is bigger than 2^32-1. Once it overflows that, another unsigned integer will be added to the array and gets the overflow. This allows the bignum implementation at least 2 advantages: 1) it can use very fast hardware types, and 2) the size of the bignum array is kept as small as possible. I could not do that for bc. Each "limb" could only hold one decimal digit, meaning that each item in the array was limited to 10^1 numbers. Obviously, that is *much* smaller than 2^32. Now, in my bc, I use unsigned chars, so my limbs are 1/4 the size of the limbs in a 32-bit-based bignum, but each limb can only use a small fraction of the range of an unsigned char. This means three things: 1) I have to manually check for overflow over 9, which adds code, 2) math on each limb in the bc takes longer than in a 32-bit-based bignum, since unsigned chars have to be zero-extended to the size of an unsigned int before doing the actual math, and 3) the amount of memory needed (on average) is much higher (though it would be astronomical if I used unsigned ints). I also have to store the location of the radix (decimal point) and sometimes perform more expensive operations when doing math on digits behind the radix. I would not have written it that way, but the POSIX bc spec mandated it. (See https://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html#tag_20_09_13_03, where it says "Internal computations shall be conducted as if in decimal, regardless of the input and output bases, to the specified number of decimal digits.") So, in essence, a bc-based bignum library is never going to be very fast. And it generally doesn't have to be; it interacts directly with a user most of the time, and users are slow compared to computers. Now, I have taken a few pains to make sure my bc is as fast as possible, under the circumstances, but the math is still the most expensive part. It's kind of freaky, actually. My parser zips through my math library fast enough that the user doesn't even notice the load lag, and though my bytecode interpreter is not slow, it is not fast either, since my parser does not optimize the bytecode. Despite that, the math is consistently taking about 80+ percent of the time, and that percentage goes *way* up when there are bigger numbers, since only addition and subtraction are linear. (I do use Karatsuba for multiplication, and it is a miracle, but it is still superlinear.) > > There are also a few > > peculiarities with the POSIX bc standard that (more or less) require a > > standalone implementation. > > > > How hard would it be to convert a bn(3)-based library to use your code? > Would there be any performance impact -- I've benchmarked bn(3) to > be pretty fast. It would not be terribly hard, but as I said above, it would not be fast at all, at least compared to a well-written hardware-based, binary bignum implementation. But if you want to, go ahead; I would appreciate the credit (though the license does not even require that). > > Also, right now I am working on getting a release candidate out that > > will enable me to make a quick port that Stefan could use as a jumping > > off point. My build system changed between 1.0 and now, and I would > > like to be able to test it. > > > > Cool. Looking forward to it. It's out. It works great. The Makefile that I sent to the mailing list a few messages back does the job well enough, though I was told in a private message not to use the GNU bc port's pkg-descr file, since it might be under the GPL. However, note that this is not the final 1.1 release; it is just for testing, even though it is high quality. Gavin Howard