Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1l1egU-0001Pl-5R for pgsql-hackers@arkaria.postgresql.org; Tue, 19 Jan 2021 00:15:46 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1l1egS-0000oZ-Ci for pgsql-hackers@arkaria.postgresql.org; Tue, 19 Jan 2021 00:15:44 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1l1egR-0000oR-Ki for pgsql-hackers@lists.postgresql.org; Tue, 19 Jan 2021 00:15:44 +0000 Received: from xvm-110-146.dc2.ghst.net ([46.226.110.146] helo=fetter.org) by makus.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1l1egM-0004CT-NI for pgsql-hackers@postgresql.org; Tue, 19 Jan 2021 00:15:42 +0000 Received: by fetter.org (Postfix, from userid 1001) id 2E33F41D34; Tue, 19 Jan 2021 01:15:36 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=fetter.org; s=default; t=1611015336; bh=XqvcM5dJ5jTpJp2XDxCYdFMIT/CPmf5B8VqNiG3zhQo=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=tDHR9crXflaN/k7cfasAtOEoe8QjgIZUpvuJb3Ctab+0HINlpsSo4AiHlstys3Tw3 jdqupHqf+maZfLcpJI9sqqHDS35J8g3TIzQqyyIpTcblqp+MCheJMReIPYtk+UuD2W vb8/pyRq6Ht+opiApPryjOraZQYDV8hM8DF9p8nxaVwEPtzt9ol9bF85e4eNDclL/1 tx9ve7AsJ8Iqsh2EA1E4HrO3ClYyOwRtcR9Xcql7Gxh+ux6Dzu2ZfXKDsd2xwrijCu 72Dl5AgwnFTvdAFMVATPNEcDnGmIiTLI9WdWDbm3wgzQ4sBfDRgE97tBQdwAw51xxc 07whc1JrLjStA== Date: Tue, 19 Jan 2021 01:15:35 +0100 From: David Fetter To: Tom Lane Cc: Peter Eisentraut , Daniel Verite , PostgreSQL Development , Vik Fearing Subject: Re: popcount Message-ID: <20210119001535.GD8721@fetter.org> References: <20201230105535.GJ13234@fetter.org> <5ea2932e-50f5-4a74-9550-5e3291b6652b@manitou-mail.org> <20201230164108.GK13234@fetter.org> <20210111161354.GA8721@fetter.org> <338981.1610984050@sss.pgh.pa.us> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="3lcZGd9BuhuYXNfi" Content-Disposition: inline In-Reply-To: <338981.1610984050@sss.pgh.pa.us> User-Agent: Mutt/1.9.4 (2018-02-28) List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk --3lcZGd9BuhuYXNfi Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Mon, Jan 18, 2021 at 10:34:10AM -0500, Tom Lane wrote: > Peter Eisentraut writes: > > [ assorted nits ] fixed, I think. > At the level of bikeshedding ... I quite dislike using the name "popcount" > for these functions. I'm aware that some C compilers provide primitives > of that name, but I wouldn't expect a SQL programmer to know that; > without that context the name seems pretty random and unintuitive. > Moreover, it invites confusion with SQL's use of "pop" to abbreviate > "population" in the statistical aggregates, such as var_pop(). > > Perhaps something along the lines of count_ones() or count_set_bits() > would be more apropos. Done that way. Best, David. -- David Fetter http://fetter.org/ Phone: +1 415 235 3778 Remember to vote! Consider donating to Postgres: http://www.postgresql.org/about/donate --3lcZGd9BuhuYXNfi Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v4-0001-popcount.patch" From 92f3d5bf1718b1b52a5a4d792f5c75e0bcc7fb74 Mon Sep 17 00:00:00 2001 From: David Fetter Date: Wed, 30 Dec 2020 02:51:46 -0800 Subject: [PATCH v4] popcount To: hackers MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------2.29.2" This is a multi-part message in MIME format. --------------2.29.2 Content-Type: text/plain; charset=UTF-8; format=fixed Content-Transfer-Encoding: 8bit Now it's accessible to SQL for the BIT VARYING and BYTEA types. diff --git doc/src/sgml/func.sgml doc/src/sgml/func.sgml index aa99665e2e..7626edeee7 100644 --- doc/src/sgml/func.sgml +++ doc/src/sgml/func.sgml @@ -4030,6 +4030,23 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three'); + + + + count_set_bits + + count_set_bits ( bytes bytea ) + bigint + + + Counts the number of bits set in a binary string. + + + count_set_bits('\xdeadbeef'::bytea) + 24 + + + @@ -4830,6 +4847,23 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three'); + + + + count_set_bits + + count_set_bits ( bits bit ) + bigint + + + Counts the bits set in a bit string. + + + count_set_bits(B'101010101010101010') + 9 + + + @@ -4869,6 +4903,7 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three'); 101010001010101010 + diff --git src/include/catalog/pg_proc.dat src/include/catalog/pg_proc.dat index b5f52d4e4a..416ee0c2fb 100644 --- src/include/catalog/pg_proc.dat +++ src/include/catalog/pg_proc.dat @@ -1446,6 +1446,9 @@ { oid => '752', descr => 'substitute portion of string', proname => 'overlay', prorettype => 'bytea', proargtypes => 'bytea bytea int4', prosrc => 'byteaoverlay_no_len' }, +{ oid => '8436', descr => 'count set bits', + proname => 'count_set_bits', prorettype => 'int8', proargtypes => 'bytea', + prosrc => 'byteapopcount'}, { oid => '725', proname => 'dist_pl', prorettype => 'float8', proargtypes => 'point line', @@ -3865,6 +3868,9 @@ { oid => '3033', descr => 'set bit', proname => 'set_bit', prorettype => 'bit', proargtypes => 'bit int4 int4', prosrc => 'bitsetbit' }, +{ oid => '8435', descr => 'count set bits', + proname => 'count_set_bits', prorettype => 'int8', proargtypes => 'bit', + prosrc => 'bitpopcount'}, # for macaddr type support { oid => '436', descr => 'I/O', diff --git src/backend/utils/adt/varbit.c src/backend/utils/adt/varbit.c index 2235866244..c9c6c73422 100644 --- src/backend/utils/adt/varbit.c +++ src/backend/utils/adt/varbit.c @@ -36,6 +36,7 @@ #include "libpq/pqformat.h" #include "nodes/nodeFuncs.h" #include "nodes/supportnodes.h" +#include "port/pg_bitutils.h" #include "utils/array.h" #include "utils/builtins.h" #include "utils/varbit.h" @@ -1878,3 +1879,30 @@ bitgetbit(PG_FUNCTION_ARGS) else PG_RETURN_INT32(0); } + +/* + * bitpopcount + * + * Returns the number of bits set in a bit string. + * + */ +Datum +bitpopcount(PG_FUNCTION_ARGS) +{ + /* There's really no chance of an overflow here because + * to get to INT64_MAX set bits, an object would have to be + * an exbibyte long, exceeding what PostgreSQL can currently + * store by a factor of 2^28 + */ + int64 popcount; + VarBit *arg1 = PG_GETARG_VARBIT_P(0); + bits8 *p; + int len; + + p = VARBITS(arg1); + len = (VARBITLEN(arg1) + BITS_PER_BYTE - 1) / BITS_PER_BYTE; + + popcount = pg_popcount((char *)p, len); + + PG_RETURN_INT64(popcount); +} diff --git src/backend/utils/adt/varlena.c src/backend/utils/adt/varlena.c index 479ed9ae54..3f1179a0e8 100644 --- src/backend/utils/adt/varlena.c +++ src/backend/utils/adt/varlena.c @@ -3439,6 +3439,22 @@ bytea_overlay(bytea *t1, bytea *t2, int sp, int sl) return result; } +/* + * popcount + */ +Datum +byteapopcount(PG_FUNCTION_ARGS) +{ + bytea *t1 = PG_GETARG_BYTEA_PP(0); + int len; + int64 result; + + len = VARSIZE_ANY_EXHDR(t1); + result = pg_popcount(VARDATA_ANY(t1), len); + + PG_RETURN_INT64(result); +} + /* * byteapos - * Return the position of the specified substring. diff --git src/test/regress/expected/bit.out src/test/regress/expected/bit.out index a7f95b846d..1187076a8d 100644 --- src/test/regress/expected/bit.out +++ src/test/regress/expected/bit.out @@ -710,6 +710,19 @@ SELECT overlay(B'0101011100' placing '001' from 20); 0101011100001 (1 row) +-- Popcount +SELECT count_set_bits(B'0101011100'::bit(10)); + count_set_bits +---------------- + 5 +(1 row) + +SELECT count_set_bits(B'1111111111'::bit(10)); + count_set_bits +---------------- + 10 +(1 row) + -- This table is intentionally left around to exercise pg_dump/pg_upgrade CREATE TABLE bit_defaults( b1 bit(4) DEFAULT '1001', diff --git src/test/regress/expected/strings.out src/test/regress/expected/strings.out index 7c91afa6e4..e94e76000b 100644 --- src/test/regress/expected/strings.out +++ src/test/regress/expected/strings.out @@ -2179,3 +2179,10 @@ SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 5 Th\000o\x02\x03 (1 row) +SET bytea_output TO hex; +SELECT count_set_bits(E'\\xdeadbeef'::bytea); + count_set_bits +---------------- + 24 +(1 row) + diff --git src/test/regress/sql/bit.sql src/test/regress/sql/bit.sql index ea01742c4a..8893d38b0d 100644 --- src/test/regress/sql/bit.sql +++ src/test/regress/sql/bit.sql @@ -215,6 +215,10 @@ SELECT overlay(B'0101011100' placing '101' from 6); SELECT overlay(B'0101011100' placing '001' from 11); SELECT overlay(B'0101011100' placing '001' from 20); +-- Popcount +SELECT count_set_bits(B'0101011100'::bit(10)); +SELECT count_set_bits(B'1111111111'::bit(10)); + -- This table is intentionally left around to exercise pg_dump/pg_upgrade CREATE TABLE bit_defaults( b1 bit(4) DEFAULT '1001', diff --git src/test/regress/sql/strings.sql src/test/regress/sql/strings.sql index ef4bfb008a..a4f7879b16 100644 --- src/test/regress/sql/strings.sql +++ src/test/regress/sql/strings.sql @@ -730,3 +730,6 @@ SELECT btrim(E'\\000trim\\000'::bytea, ''::bytea); SELECT encode(overlay(E'Th\\000omas'::bytea placing E'Th\\001omas'::bytea from 2),'escape'); SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 8),'escape'); SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 5 for 3),'escape'); + +SET bytea_output TO hex; +SELECT count_set_bits(E'\\xdeadbeef'::bytea); --------------2.29.2-- --3lcZGd9BuhuYXNfi--