[PATCH v2 0/6] crda: few more updates

[PATCH v2 0/6] crda: few more updates

[Luis R. Rodriguez]

Here's a second spin, after quite a bit more testing I ran
into a few small issues with the parser and library. This
has these additional fixes / enhancements:

  * Lifts the restriction on 32 rules, although the kernel
    is limited by this we don't adhere to this limit on our
    stream parser or optimizer

  * The union code got updated to address two cases that are
    invalid for unions

  * A few fixes on db2rd and optimizer on using the stream
    parser, if its NULL, bail, we weren't checking for it

  * The optimizer was not considering band differences as
    part of its key broker (when it decides it can use
    two rules for optimization), to address this we deduce
    the band and add that to the key mixing. Note that this
    will need to be updated upon new frequency band additions.
    This limits the scope of optimizations between their own
    respective bands.

I've also gone ahead and tested this with a huge fluffy
non optimized regulatory domain of 40 rules, and also with
the wireless-regdb db.txt. I'll send some optimizations
based on this for wireless-regdb.

The only patches that go modified are the stream parser
and the optimizer.

Luis R. Rodriguez (6):
  crda: relicense under copyleft-next-0.3.0
  crda: fix -pedantic gcc compilation
  crda: add regulatory domain stream parser
  crda: add regulatory domain optimizer
  crda: make ssl keys include stdint.h
  crda: make reglib a shared library

 LICENSE             |  14 +-
 Makefile            |  54 +++-
 copyleft-next-0.3.0 | 219 ++++++++++++++
 crda.c              |   4 +-
 db2rd.c             |  32 ++
 optimize.c          |  40 +++
 reglib.c            | 839 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 reglib.h            |  60 ++++
 utils/key2pub.py    |   2 +
 9 files changed, 1252 insertions(+), 12 deletions(-)
 create mode 100644 copyleft-next-0.3.0
 create mode 100644 db2rd.c
 create mode 100644 optimize.c

-- 
1.8.4.rc3

[PATCH v2 1/6] crda: relicense under copyleft-next-0.3.0

[Luis R. Rodriguez]

I'm relicensing CRDA to copyleft-next-0.3.0. The original
motivation was to help with the BSD family but they are not
using any of this software and as this software grows I'd
like to ensure we use the best free software license
possible.

Fontana's work on copyleft-next is great and has good
community traction. At this point development for
copyleft-next has slowed down as copyleft-next-0.3.0
is already a good, usable alternative to GPLv2 and GPLv3.

A few notes:

  * With copyleft we don't have to specify 'at your option
    any later version' since the license allows that by
    default.

  * Some folks might wonder if copyleft-next-0.3.0 is
    OSI OSD-conformant or FSF-free since neither of
    those bodies have examined the license officially,
    but note, although IANAL, that copyleft-next is
    outbound-compatible with GPLv2 and GPLv3

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 LICENSE             |  14 +++-
 copyleft-next-0.3.0 | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 232 insertions(+), 1 deletion(-)
 create mode 100644 copyleft-next-0.3.0

diff --git a/LICENSE b/LICENSE
index 652a6dd..cc26ff2 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,4 +1,16 @@
-Copyright (c) 2008, Luis R. Rodriguez <mcgrof@gmail.com>
+Copyright (c) 2013, Luis R. Rodriguez <mcgrof@do-not-panic.com>
+
+CRDA is licensed under copyleft-next 0.3.0
+
+Refer to copyleft-next-0.3.0 for license details, you can
+also always get the latest updates of copyleft-next from:
+
+https://gitorious.org/copyleft-next/
+
+This file incorporates work covered by the following copyright and
+permission notice:
+
+Copyright (c) 2008, Luis R. Rodriguez <mcgrof@do-not-panic.com>
 Copyright (c) 2008, Johannes Berg <johannes@sipsolutions.net>
 Copyright (c) 2008, Michael Green <Michael.Green@Atheros.com>
 
diff --git a/copyleft-next-0.3.0 b/copyleft-next-0.3.0
new file mode 100644
index 0000000..a66d5bf
--- /dev/null
+++ b/copyleft-next-0.3.0
@@ -0,0 +1,219 @@
+                   copyleft-next 0.3.0 ("this License")
+                         Release date: 2013-05-16
+
+1. License Grants; No Trademark License
+
+   Subject to the terms of this License, I grant You:
+
+   a) A non-exclusive, worldwide, perpetual, royalty-free, irrevocable
+      copyright license, to reproduce, Distribute, prepare derivative works
+      of, publicly perform and publicly display My Work.
+
+   b) A non-exclusive, worldwide, perpetual, royalty-free, irrevocable
+      patent license under Licensed Patents to make, have made, use, sell,
+      offer for sale, and import Covered Works.
+
+   This License does not grant any rights in My name, trademarks, service
+   marks, or logos.
+
+2. Distribution: General Conditions
+
+   You may Distribute Covered Works, provided that You (i) inform
+   recipients how they can obtain a copy of this License; (ii) satisfy the
+   applicable conditions of sections 3 through 6; and (iii) preserve all
+   Legal Notices contained in My Work (to the extent they remain
+   pertinent). "Legal Notices" means copyright notices, license notices,
+   license texts, and author attributions, but does not include logos,
+   other graphical images, trademarks or trademark legends.
+
+3. Conditions for Distributing Derived Works; Outbound GPL Compatibility
+
+   If You Distribute a Derived Work, You must license the entire Derived
+   Work as a whole under this License, with prominent notice of such
+   licensing. This condition may not be avoided through such means as
+   separate Distribution of portions of the Derived Work. You may
+   additionally license the Derived Work under the GPL, so that the
+   recipient may further Distribute the Derived Work under either this
+   License or the GPL.
+
+4. Condition Against Further Restrictions; Inbound License Compatibility
+
+   When Distributing a Covered Work, You may not impose further
+   restrictions on the exercise of rights in the Covered Work granted under
+   this License. This condition is not excused merely because such
+   restrictions result from Your compliance with conditions or obligations
+   extrinsic to this License (such as a court order or an agreement with a
+   third party).
+
+   However, You may Distribute a Covered Work incorporating material
+   governed by a license that is both OSI-Approved and FSF-Free as of the
+   release date of this License, provided that Your Distribution complies
+   with such other license.
+
+5. Conditions for Distributing Object Code
+
+   You may Distribute an Object Code form of a Covered Work, provided that
+   you accompany the Object Code with a URL through which the Corresponding
+   Source is made available, at no charge, by some standard or customary
+   means of providing network access to source code.
+
+   If you Distribute the Object Code in a physical product or tangible
+   storage medium ("Product"), the Corresponding Source must be available
+   through such URL for two years from the date of Your most recent
+   Distribution of the Object Code in the Product. However, if the Product
+   itself contains or is accompanied by the Corresponding Source (made
+   available in a customarily accessible manner), You need not also comply
+   with the first paragraph of this section.
+
+   Each recipient of the Covered Work from You is an intended third-party
+   beneficiary of this License solely as to this section 5, with the right
+   to enforce its terms.
+
+6. Symmetrical Licensing Condition for Upstream Contributions
+
+   If You Distribute a work to Me specifically for inclusion in or
+   modification of a Covered Work (a "Patch"), and no explicit licensing
+   terms apply to the Patch, You license the Patch under this License, to
+   the extent of Your copyright in the Patch. This condition does not
+   negate the other conditions of this License, if applicable to the Patch.
+
+7. Nullification of Copyleft/Proprietary Dual Licensing
+
+   If I offer to license, for a fee, a Covered Work under terms other than
+   a license that is OSI-Approved or FSF-Free as of the release date of this
+   License or a numbered version of copyleft-next released by the
+   Copyleft-Next Project, then the license I grant You under section 1 is no
+   longer subject to the conditions in sections 2 through 5.
+
+8. Copyleft Sunset
+
+   The conditions in sections 2 through 5 no longer apply once fifteen
+   years have elapsed from the date of My first Distribution of My Work
+   under this License.
+
+9. Pass-Through
+
+   When You Distribute a Covered Work, the recipient automatically receives
+   a license to My Work from Me, subject to the terms of this License.
+
+10. Termination
+
+    Your license grants under section 1 are automatically terminated if You
+
+    a) fail to comply with the conditions of this License, unless You cure
+       such noncompliance within thirty days after becoming aware of it, or
+
+    b) initiate a patent infringement litigation claim (excluding
+       declaratory judgment actions, counterclaims, and cross-claims)
+       alleging that any part of My Work directly or indirectly infringes
+       any patent.
+
+    Termination of Your license grants extends to all copies of Covered
+    Works You subsequently obtain. Termination does not terminate the
+    rights of those who have received copies or rights from You subject to
+    this License.
+
+    To the extent permission to make copies of a Covered Work is necessary
+    merely for running it, such permission is not terminable.
+
+11. Later License Versions
+
+    The Copyleft-Next Project may release new versions of copyleft-next,
+    designated by a distinguishing version number ("Later Versions").
+    Unless I explicitly remove the option of Distributing Covered Works
+    under Later Versions, You may Distribute Covered Works under any Later
+    Version.
+
+** 12. No Warranty                                                       **
+**                                                                       **
+**     My Work is provided "as-is", without warranty. You bear the risk  **
+**     of using it. To the extent permitted by applicable law, each      **
+**     Distributor of My Work excludes the implied warranties of title,  **
+**     merchantability, fitness for a particular purpose and             **
+**     non-infringement.                                                 **
+
+** 13. Limitation of Liability                                           **
+**                                                                       **
+**     To the extent permitted by applicable law, in no event will any   **
+**     Distributor of My Work be liable to You for any damages           **
+**     whatsoever, whether direct, indirect, special, incidental, or     **
+**     consequential damages, whether arising under contract, tort       **
+**     (including negligence), or otherwise, even where the Distributor  **
+**     knew or should have known about the possibility of such damages.  **
+
+14. Severability
+
+    The invalidity or unenforceability of any provision of this License
+    does not affect the validity or enforceability of the remainder of
+    this License. Such provision is to be reformed to the minimum extent
+    necessary to make it valid and enforceable.
+
+15. Definitions
+
+    "Copyleft-Next Project" means the project that maintains the source
+    code repository at <https://gitorious.org/copyleft-next/> as of the
+    release date of this License.
+
+    "Corresponding Source" of a Covered Work in Object Code form means (i)
+    the Source Code form of the Covered Work; (ii) all scripts,
+    instructions and similar information that are reasonably necessary for
+    a skilled developer to generate such Object Code from the Source Code
+    provided under (i); and (iii) a list clearly identifying all Separate
+    Works (other than those provided in compliance with (ii)) that were
+    specifically used in building and (if applicable) installing the
+    Covered Work (for example, a specified proprietary compiler including
+    its version number). Corresponding Source must be machine-readable.
+
+    "Covered Work" means My Work or a Derived Work.
+
+    "Derived Work" means a work of authorship that copies from, modifies,
+    adapts, is based on, is a derivative work of, transforms, translates or
+    contains all or part of My Work, such that copyright permission is
+    required. The following are not Derived Works: (i) Mere Aggregation;
+    (ii) a mere reproduction of My Work; and (iii) if My Work fails to
+    explicitly state an expectation otherwise, a work that merely makes
+    reference to My Work.
+
+    "Distribute" means to distribute, transfer or make a copy available to
+    someone else, such that copyright permission is required.
+
+    "Distributor" means Me and anyone else who Distributes a Covered Work.
+
+    "FSF-Free" means classified as 'free' by the Free Software Foundation.
+
+    "GPL" means a version of the GNU General Public License or the GNU
+    Affero General Public License.
+
+    "I"/"Me"/"My" refers to the individual or legal entity that places My
+    Work under this License. "You"/"Your" refers to the individual or legal
+    entity exercising rights in My Work under this License. A legal entity
+    includes each entity that controls, is controlled by, or is under
+    common control with such legal entity. "Control" means (a) the power to
+    direct the actions of such legal entity, whether by contract or
+    otherwise, or (b) ownership of more than fifty percent of the
+    outstanding shares or beneficial ownership of such legal entity.
+
+    "Licensed Patents" means all patent claims licensable royalty-free by
+    Me, now or in the future, that are necessarily infringed by making,
+    using, or selling My Work, and excludes claims that would be infringed
+    only as a consequence of further modification of My Work.
+
+    "Mere Aggregation" means an aggregation of a Covered Work with a
+    Separate Work.
+
+    "My Work" means the particular work of authorship I license to You
+    under this License.
+
+    "Object Code" means any form of a work that is not Source Code.
+
+    "OSI-Approved" means approved as 'Open Source' by the Open Source
+    Initiative.
+
+    "Separate Work" means a work that is separate from and independent of a
+    particular Covered Work and is not by its nature an extension or
+    enhancement of the Covered Work, and/or a runtime library, standard
+    library or similar component that is used to generate an Object Code
+    form of a Covered Work.
+
+    "Source Code" means the preferred form of a work for making
+    modifications to it.
-- 
1.8.4.rc3

[PATCH v2 2/6] crda: fix -pedantic gcc compilation

[Luis R. Rodriguez]

gcc likes to complain about this, fix that as we're
going to get a bit more anal with code here soon as
we're moving towards making a library out of reglib.

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 crda.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/crda.c b/crda.c
index 2a601eb..4751a39 100644
--- a/crda.c
+++ b/crda.c
@@ -141,13 +141,15 @@ int main(int argc, char **argv)
 {
 	int fd = -1;
 	int i = 0, j, r;
-	char alpha2[3] = {}; /* NUL-terminate */
+	char alpha2[3];
 	char *env_country;
 	struct nl80211_state nlstate;
 	struct nl_cb *cb = NULL;
 	struct nl_msg *msg;
 	int finished = 0;
 
+	memset(alpha2, 0, 3);
+
 	struct nlattr *nl_reg_rules;
 	const struct ieee80211_regdomain *rd = NULL;
 
-- 
1.8.4.rc3

[PATCH v2 3/6] crda: add regulatory domain stream parser

[Luis R. Rodriguez]

This adds a stream parser for regulatory domains. This
allows developers to build regulatory domains now using
the db.txt from a stream, either stdin, or a from an
opened file.

This also adds a simple db2rd which for now only uses the
library but with a bit of effort can also be used as a
suitable replacement for the kernel's genregdb.awk.

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 Makefile |  10 +-
 db2rd.c  |  32 ++++
 reglib.c | 543 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 reglib.h |  44 ++++++
 4 files changed, 627 insertions(+), 2 deletions(-)
 create mode 100644 db2rd.c

diff --git a/Makefile b/Makefile
index 7d2e33f..bd9c220 100644
--- a/Makefile
+++ b/Makefile
@@ -24,10 +24,11 @@ PUBKEY_DIR?=pubkeys
 RUNTIME_PUBKEY_DIR?=/etc/wireless-regdb/pubkeys
 
 CFLAGS += -Wall -g
+LDLIBS += -lm
 
 all: all_noverify verify
 
-all_noverify: crda intersect regdbdump
+all_noverify: crda intersect regdbdump db2rd
 
 ifeq ($(USE_OPENSSL),1)
 CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl`
@@ -121,6 +122,10 @@ intersect: reglib.o intersect.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
+db2rd: reglib.o db2rd.o
+	$(NQ) '  LD  ' $@
+	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
+
 verify: $(REG_BIN) regdbdump
 	$(NQ) '  CHK  $(REG_BIN)'
 	$(Q)./regdbdump $(REG_BIN) >/dev/null
@@ -152,5 +157,6 @@ install: crda crda.8.gz regdbdump.8.gz
 	$(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz
 
 clean:
-	$(Q)rm -f crda regdbdump intersect *.o *~ *.pyc keys-*.c *.gz \
+	$(Q)rm -f crda regdbdump intersect db2rd \
+		*.o *~ *.pyc keys-*.c *.gz \
 	udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
diff --git a/db2rd.c b/db2rd.c
new file mode 100644
index 0000000..51ec051
--- /dev/null
+++ b/db2rd.c
@@ -0,0 +1,32 @@
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <arpa/inet.h> /* ntohl */
+#include <string.h>
+
+#include "nl80211.h"
+#include "reglib.h"
+
+int main(int argc, char **argv)
+{
+	struct ieee80211_regdomain *rd = NULL;
+	FILE *fp;
+
+	if (argc != 1) {
+		fprintf(stderr, "Usage: cat db.txt | %s\n", argv[0]);
+		return -EINVAL;
+	}
+
+	fp = reglib_create_parse_stream(stdin);
+	if (!fp)
+		return -EINVAL;
+
+	reglib_for_each_country_stream(fp, rd) {
+		reglib_print_regdom(rd);
+		free(rd);
+	}
+
+	fclose(fp);
+
+	return 0;
+}
diff --git a/reglib.c b/reglib.c
index b0c61e5..6191acd 100644
--- a/reglib.c
+++ b/reglib.c
@@ -38,6 +38,19 @@
 #include "keys-gcrypt.c"
 #endif
 
+int debug = 0;
+
+struct reglib_rule_parse_list {
+	int n_parsers;
+	int (*rule_parsers[])(char *line, struct ieee80211_reg_rule *reg_rule);
+};
+
+struct reglib_country_parse_list {
+	int n_parsers;
+	int (*country_parsers[])(char *line, struct ieee80211_regdomain *rd);
+};
+
+
 void *
 reglib_get_file_ptr(uint8_t *db, size_t dblen, size_t structlen, uint32_t ptr)
 {
@@ -707,3 +720,533 @@ void reglib_print_regdom(const struct ieee80211_regdomain *rd)
 		print_reg_rule(&rd->reg_rules[i]);
 	printf("\n");
 }
+
+static unsigned int reglib_parse_dfs_region(char *dfs_region)
+{
+	if (strncmp(dfs_region, "DFS-FCC", 7) == 0)
+		return REGDB_DFS_FCC;
+	if (strncmp(dfs_region, "DFS-ETSI", 8) == 0)
+		return REGDB_DFS_ETSI;
+	if (strncmp(dfs_region, "DFS-JP", 6) == 0)
+		return REGDB_DFS_JP;
+	return REGDB_DFS_UNSET;
+}
+
+static uint32_t reglib_parse_rule_flag(char *flag_s)
+{
+	if (strncmp(flag_s, "NO-OFDM", 7) == 0)
+		return RRF_NO_OFDM;
+	if (strncmp(flag_s, "NO-CCK", 6) == 0)
+		return RRF_NO_CCK;
+	if (strncmp(flag_s, "NO-INDOOR", 9) == 0)
+		return RRF_NO_INDOOR;
+	if (strncmp(flag_s, "NO-OUTDOOR", 10) == 0)
+		return RRF_NO_OUTDOOR;
+	if (strncmp(flag_s, "DFS", 3) == 0)
+		return RRF_DFS;
+	if (strncmp(flag_s, "PTP-ONLY", 8) == 0)
+		return RRF_PTP_ONLY;
+	if (strncmp(flag_s, "PTMP-ONLY", 9) == 0)
+		return RRF_PTMP_ONLY;
+	if (strncmp(flag_s, "NO-IR", 5) == 0)
+		return RRF_NO_IR;
+
+	return 0;
+}
+
+static int
+reglib_parse_rule_simple(char *line, struct ieee80211_reg_rule *reg_rule)
+{
+	int hits;
+	float start_freq_khz, end_freq_khz, max_bandwidth_khz, max_eirp;
+
+	hits = sscanf(line, "\t(%f - %f @ %f), (%f)\n",
+		      &start_freq_khz,
+		      &end_freq_khz,
+		      &max_bandwidth_khz,
+		      &max_eirp);
+
+	if (hits != 4)
+		return -EINVAL;
+
+	reg_rule->freq_range.start_freq_khz =
+		REGLIB_MHZ_TO_KHZ(start_freq_khz);
+	reg_rule->freq_range.end_freq_khz =
+		REGLIB_MHZ_TO_KHZ(end_freq_khz);
+	reg_rule->freq_range.max_bandwidth_khz =
+		REGLIB_MHZ_TO_KHZ(max_bandwidth_khz);
+	reg_rule->power_rule.max_eirp =
+		REGLIB_DBM_TO_MBM(max_eirp);
+
+	reg_rule->flags = 0;
+
+	if (debug)
+		printf("reglib_parse_rule_simple(): %d line: %s", hits, line);
+
+
+	return 0;
+}
+
+static int
+reglib_parse_rule_simple_mw(char *line, struct ieee80211_reg_rule *reg_rule)
+{
+	int hits;
+	float start_freq_khz, end_freq_khz, max_bandwidth_khz, max_eirp;
+	char mw[3];
+
+	hits = sscanf(line, "\t(%f - %f @ %f), (%f %2[mW])\n",
+		      &start_freq_khz,
+		      &end_freq_khz,
+		      &max_bandwidth_khz,
+		      &max_eirp, mw);
+
+	if (hits != 4)
+		return -EINVAL;
+
+
+	reg_rule->freq_range.start_freq_khz =
+		REGLIB_MHZ_TO_KHZ(start_freq_khz);
+	reg_rule->freq_range.end_freq_khz =
+		REGLIB_MHZ_TO_KHZ(end_freq_khz);
+	reg_rule->freq_range.max_bandwidth_khz =
+		REGLIB_MHZ_TO_KHZ(max_bandwidth_khz);
+	reg_rule->power_rule.max_eirp =
+		REGLIB_MW_TO_MBM(max_eirp);
+
+	reg_rule->flags = 0;
+
+	if (debug)
+		printf("reglib_parse_rule_simple_mw(): %d line: %s",
+		       hits, line);
+
+	return 0;
+}
+
+static int
+reglib_parse_rule_args(char *line, struct ieee80211_reg_rule *reg_rule)
+{
+#define IGNORE_COMMA_OR_SPACE "%*[ ,]"
+	int hits;
+	char flag_list[9][100];
+	unsigned int i = 0;
+	float start_freq_khz, end_freq_khz, max_bandwidth_khz, max_eirp;
+
+	for (i = 0; i < 9; i++)
+		memset(flag_list[i], 0, sizeof(flag_list[i]));
+
+	hits = sscanf(line, "\t(%f - %f @ %f), (%f)"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s",
+		      &start_freq_khz,
+		      &end_freq_khz,
+		      &max_bandwidth_khz,
+		      &max_eirp,
+		      flag_list[0],
+		      flag_list[1],
+		      flag_list[2],
+		      flag_list[3],
+		      flag_list[4],
+		      flag_list[5],
+		      flag_list[6],
+		      flag_list[7],
+		      flag_list[8]);
+
+	if (hits < 5)
+		return -EINVAL;
+
+	reg_rule->freq_range.start_freq_khz =
+		REGLIB_MHZ_TO_KHZ(start_freq_khz);
+	reg_rule->freq_range.end_freq_khz =
+		REGLIB_MHZ_TO_KHZ(end_freq_khz);
+	reg_rule->freq_range.max_bandwidth_khz =
+		REGLIB_MHZ_TO_KHZ(max_bandwidth_khz);
+	reg_rule->power_rule.max_eirp =
+		REGLIB_DBM_TO_MBM(max_eirp);
+
+	for (i = 0; i < 8; i++)
+		reg_rule->flags |= reglib_parse_rule_flag(flag_list[i]);
+
+	if (debug)
+		printf("reglib_parse_rule_args(): %d flags: %d, line: %s",
+		       hits, reg_rule->flags, line);
+
+	return 0;
+#undef IGNORE_COMMA_OR_SPACE
+}
+
+
+static int
+reglib_parse_rule_args_mw(char *line, struct ieee80211_reg_rule *reg_rule)
+{
+#define IGNORE_COMMA_OR_SPACE "%*[ ,]"
+	int hits;
+	char flag_list[9][100];
+	unsigned int i = 0;
+	char mw[3];
+	float start_freq_khz, end_freq_khz, max_bandwidth_khz, max_eirp;
+
+	for (i = 0; i < 9; i++)
+		memset(flag_list[i], 0, sizeof(flag_list[i]));
+
+	hits = sscanf(line, "\t(%f - %f @ %f), (%f %2[mW])"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s"
+		      IGNORE_COMMA_OR_SPACE "%s",
+		      &start_freq_khz,
+		      &end_freq_khz,
+		      &max_bandwidth_khz,
+		      &max_eirp,
+		      mw,
+		      flag_list[0],
+		      flag_list[1],
+		      flag_list[2],
+		      flag_list[3],
+		      flag_list[4],
+		      flag_list[5],
+		      flag_list[6],
+		      flag_list[7],
+		      flag_list[8]);
+
+	if (hits < 5)
+		return -EINVAL;
+
+	reg_rule->freq_range.start_freq_khz =
+		REGLIB_MHZ_TO_KHZ(start_freq_khz);
+	reg_rule->freq_range.end_freq_khz =
+		REGLIB_MHZ_TO_KHZ(end_freq_khz);
+	reg_rule->freq_range.max_bandwidth_khz =
+		REGLIB_MHZ_TO_KHZ(max_bandwidth_khz);
+	reg_rule->power_rule.max_eirp =
+		REGLIB_MW_TO_MBM(max_eirp);
+
+	for (i = 0; i < 8; i++)
+		reg_rule->flags |= reglib_parse_rule_flag(flag_list[i]);
+
+	if (debug)
+		printf("reglib_parse_rule_args_mw(): %d flags: %d, line: %s",
+		       hits, reg_rule->flags, line);
+	return 0;
+#undef IGNORE_COMMA_OR_SPACE
+}
+
+static int reglib_parse_rule(FILE *fp, struct ieee80211_reg_rule *reg_rule)
+{
+	char line[1024];
+	char *line_p;
+	unsigned int i;
+	int r = 0;
+	struct reglib_rule_parse_list *reglib_rule_parsers;
+	size_t size_parsers = sizeof(struct reglib_rule_parse_list) + 
+				4 * sizeof(int (*)(char *, struct ieee80211_reg_rule *));
+
+	reglib_rule_parsers = malloc(size_parsers);
+	if (!reglib_rule_parsers)
+		return -EINVAL;
+	memset(reglib_rule_parsers, 0, size_parsers);
+
+	reglib_rule_parsers->n_parsers = 4;
+
+	/*
+	 * XXX: sscanf() is a bit odd with picking up mW
+	 * case over the simple one, this order however works,
+	 * gotta figure out how to be more precise.
+	 */
+	reglib_rule_parsers->rule_parsers[0] = reglib_parse_rule_args_mw;
+	reglib_rule_parsers->rule_parsers[1] = reglib_parse_rule_args;
+	reglib_rule_parsers->rule_parsers[2] = reglib_parse_rule_simple;
+	reglib_rule_parsers->rule_parsers[3] = reglib_parse_rule_simple_mw;
+
+	memset(line, 0, sizeof(line));
+	line_p = fgets(line, sizeof(line), fp);
+	if (line_p != line)
+		return -EINVAL;
+
+	for (i = 0; i < reglib_rule_parsers->n_parsers; i++) {
+		r = reglib_rule_parsers->rule_parsers[i](line, reg_rule);
+		if (r == 0)
+			break;
+	}
+
+	return r;
+}
+
+static uint32_t
+reglib_get_n_rules(FILE *fp, struct ieee80211_reg_rule *reg_rule)
+{
+	uint32_t n_rules = 0;
+	int r;
+	bool save_debug = false;
+
+	save_debug = debug;
+	debug = false;
+
+	while (1) {
+		r = reglib_parse_rule(fp, reg_rule);
+		if (r != 0)
+			break;
+		n_rules++;
+	}
+
+	debug = save_debug;
+
+	return n_rules;
+}
+
+static int reglib_parse_reg_rule(FILE *fp, struct ieee80211_reg_rule *reg_rule)
+{
+	int r;
+
+	while (1) {
+		r = reglib_parse_rule(fp, reg_rule);
+		if (r != 0)
+			continue;
+		return 0;
+	}
+}
+
+static struct ieee80211_regdomain *
+reglib_parse_rules(FILE *fp, struct ieee80211_regdomain *trd)
+{
+	struct ieee80211_regdomain *rd;
+	struct ieee80211_reg_rule rule;
+	struct ieee80211_reg_rule *reg_rule;
+	fpos_t pos;
+	unsigned int i;
+	uint32_t size_of_regd = 0, num_rules = 0;
+	int r;
+
+	memset(&rule, 0, sizeof(rule));
+	reg_rule = &rule;
+
+	r = fgetpos(fp, &pos);
+	if (r != 0) {
+		fprintf(stderr, "fgetpos() failed: %s\n",
+			strerror(errno));
+		return NULL;
+	}
+
+	num_rules = reglib_get_n_rules(fp, reg_rule);
+	if (!num_rules)
+		return NULL;
+
+	size_of_regd = reglib_array_len(sizeof(struct ieee80211_regdomain),
+					num_rules + 1,
+					sizeof(struct ieee80211_reg_rule));
+	rd = malloc(size_of_regd);
+	if (!rd)
+		return NULL;
+
+	memset(rd, 0, size_of_regd);
+	memcpy(rd, trd, sizeof(*trd));
+
+	rd->n_reg_rules = num_rules;
+
+	r = fsetpos(fp, &pos);
+	if (r != 0) {
+		fprintf(stderr, "fsetpos() failed: %s\n",
+			strerror(errno));
+		free(rd);
+		return NULL;
+	}
+	for (i = 0; i < num_rules; i++) {
+		struct ieee80211_reg_rule *rrule = &rd->reg_rules[i];
+
+		if (reglib_parse_reg_rule(fp, rrule) != 0) {
+			fprintf(stderr, "rule parse failed\n");
+			free(rd);
+			return NULL;
+		}
+	}
+	return rd;
+}
+
+static int
+reglib_parse_country_simple(char *line, struct ieee80211_regdomain *rd)
+{
+	char dfs_region_alpha[9];
+	char alpha2[2];
+	int hits;
+
+	memset(rd, 0, sizeof(rd));
+	memset(alpha2, 0, sizeof(alpha2));
+	memset(dfs_region_alpha, 0, sizeof(dfs_region_alpha));
+
+	hits = sscanf(line, "country %2[a-zA-Z0-9]:",
+		      alpha2);
+
+	if (hits != 1)
+		return -EINVAL;
+
+	rd->alpha2[0] = alpha2[0];
+	rd->alpha2[1] = alpha2[1];
+
+	return 0;
+}
+
+static int reglib_parse_country_dfs(char *line, struct ieee80211_regdomain *rd)
+{
+	char dfs_region_alpha[9];
+	char alpha2[2];
+	int hits;
+
+	memset(rd, 0, sizeof(rd));
+	memset(alpha2, 0, sizeof(alpha2));
+	memset(dfs_region_alpha, 0, sizeof(dfs_region_alpha));
+
+	hits = sscanf(line, "country %2[a-zA-Z0-9]:%*[ ]%s\n",
+		      alpha2,
+		      dfs_region_alpha);
+	if (hits <= 0)
+		return -EINVAL;
+
+	if (hits != 2)
+		return -EINVAL;
+
+
+	rd->alpha2[0] = alpha2[0];
+	rd->alpha2[1] = alpha2[1];
+	rd->dfs_region = reglib_parse_dfs_region(dfs_region_alpha);
+
+	return 0;
+}
+
+struct ieee80211_regdomain *__reglib_parse_country(FILE *fp)
+{
+	struct ieee80211_regdomain *rd;
+	struct ieee80211_regdomain tmp_rd;
+	char line[1024];
+	char *line_p;
+	unsigned int i;
+	int r = 0;
+	struct reglib_country_parse_list *reglib_country_parsers;
+	size_t size_of_parsers = sizeof(struct reglib_country_parse_list) +
+					2 * sizeof(int (*)(char *, struct ieee80211_regdomain *));
+
+	reglib_country_parsers = malloc(size_of_parsers);
+	if (!reglib_country_parsers)
+		return NULL;
+	memset(reglib_country_parsers, 0, size_of_parsers);
+
+	reglib_country_parsers->n_parsers = 2;
+	reglib_country_parsers->country_parsers[0] =
+			reglib_parse_country_dfs;
+	reglib_country_parsers->country_parsers[1] =
+			reglib_parse_country_simple;
+
+	memset(&tmp_rd, 0, sizeof(tmp_rd));
+	memset(line, 0, sizeof(line));
+
+	line_p = fgets(line, sizeof(line), fp);
+
+	if (line_p != line)
+		return NULL;
+
+	for (i = 0; i < reglib_country_parsers->n_parsers; i++) {
+		r = reglib_country_parsers->country_parsers[i](line, &tmp_rd);
+		if (r == 0)
+			break;
+	}
+
+	if (r != 0) {
+		fprintf(stderr, "Invalid country line: %s", line);
+		return NULL;
+	}
+
+	rd = reglib_parse_rules(fp, &tmp_rd);
+
+	return rd;
+}
+
+static int reglib_find_next_country_stream(FILE *fp)
+{
+	fpos_t prev_pos;
+	int r;
+	unsigned int i = 0;
+
+	while(1) {
+		char line[1024];
+		char *line_p;
+
+		r = fgetpos(fp, &prev_pos);
+		if (r != 0) {
+			fprintf(stderr, "fgetpos() failed: %s\n",
+				strerror(errno));
+			return r;
+		}
+
+		memset(line, 0, sizeof(line));
+
+		line_p = fgets(line, sizeof(line), fp);
+		if (line_p == line) {
+			if (strspn(line, "\n") == strlen(line)) {
+				i++;
+				continue;
+			}
+			if (strncmp(line, "country", 7) != 0)
+				continue;
+			r = fsetpos(fp, &prev_pos);
+			if (r != 0) {
+				fprintf(stderr, "fsetpos() failed: %s\n",
+					strerror(errno));
+				return r;
+			}
+			return 0;
+		} else
+			return EOF;
+	}
+}
+
+struct ieee80211_regdomain *reglib_parse_country(FILE *fp)
+{
+	int r;
+
+	r = reglib_find_next_country_stream(fp);
+	if (r != 0)
+		return NULL;
+	return __reglib_parse_country(fp);
+}
+
+FILE *reglib_create_parse_stream(FILE *f)
+{
+	unsigned int lines = 0;
+	FILE *fp;
+
+	fp = tmpfile();
+	if (errno) {
+		fprintf(stderr, "%s\n", strerror(errno));
+		return NULL;
+	}
+
+	while(1) {
+		char line[1024];
+		char *line_p;
+
+		line_p = fgets(line, sizeof(line), f);
+		if (line_p == line) {
+			if (strchr(line, '#') == NULL) {
+				fputs(line, fp);
+				lines++;
+			}
+			continue;
+		} else
+			break;
+	}
+
+	rewind(fp);
+	fflush(fp);
+
+	return fp;
+}
diff --git a/reglib.h b/reglib.h
index 7a586a3..885792e 100644
--- a/reglib.h
+++ b/reglib.h
@@ -1,10 +1,12 @@
 #ifndef REG_LIB_H
 #define REG_LIB_H
 
+#include <stdio.h>
 #include <stdlib.h>
 #include <stdint.h>
 #include <stdbool.h>
 #include <sys/stat.h>
+#include <math.h>
 
 #include "regdb.h"
 
@@ -35,6 +37,19 @@ struct ieee80211_regdomain {
 	struct ieee80211_reg_rule reg_rules[];
 };
 
+/* Remove this once upstream nl80211.h gets this */
+#define NL80211_RRF_NO_IR (1<<7)
+
+#define REGLIB_MHZ_TO_KHZ(freq) ((freq) * 1000)
+#define REGLIB_KHZ_TO_MHZ(freq) ((freq) / 1000)
+#define REGLIB_DBI_TO_MBI(gain) ((gain) * 100)
+#define REGLIB_MBI_TO_DBI(gain) ((gain) / 100)
+#define REGLIB_DBM_TO_MBM(gain) ((gain) * 100)
+#define REGLIB_MBM_TO_DBM(gain) ((gain) / 100)
+
+#define REGLIB_MW_TO_DBM(gain) (10 * log10(gain))
+#define REGLIB_MW_TO_MBM(gain) (REGLIB_DBM_TO_MBM(REGLIB_MW_TO_DBM(gain)))
+
 /**
  * struct reglib_regdb_ctx - reglib regdb context
  *
@@ -180,4 +195,33 @@ reglib_intersect_rds(const struct ieee80211_regdomain *rd1,
 const struct ieee80211_regdomain *
 reglib_intersect_regdb(const struct reglib_regdb_ctx *ctx);
 
+/**
+ * @reglib_create_parse_stream - provide a clean new stream for processing
+ *
+ * @fp: FILE stream, could be stdin, or a stream from an open file.
+ *
+ * In order to parse a stream we recommend to create a new stream
+ * using this helper. A new stream is preferred in order to work
+ * with stdin, as otherwise we cannot rewind() and move around
+ * the stream. This helper will create new stream using tmpfile()
+ * and also remove all comments. It will be closed and the file
+ * deleted when the process terminates.
+ */
+FILE *reglib_create_parse_stream(FILE *fp);
+
+/**
+ * @reglib_parse_country - parse stream to build a regulatory domain
+ *
+ * @fp: FILE stream, could be stdin, or a stream from an open file.
+ *
+ * Parse stream and return back a built regulatory domain. Returns
+ * NULL if one could not be built.
+ */
+struct ieee80211_regdomain *reglib_parse_country(FILE *fp);
+
+#define reglib_for_each_country_stream(__fp, __rd)		\
+	for (__rd = reglib_parse_country(__fp);			\
+	     __rd != NULL;					\
+	     __rd = reglib_parse_country(__fp))			\
+
 #endif
-- 
1.8.4.rc3

[PATCH v2 4/6] crda: add regulatory domain optimizer

[Luis R. Rodriguez]

This adds a regulatory domain optimizer which can be
used with information of a regulatory domain in db.txt
format in stdin. It makes use of the new shiny regulatory
domain stream parser.

The way this works is it iterates over the regulatory domain
computing unions between each frequency, starting from each
frequency as a pivot. If a union leads to a valid regulatory
rule we verify that the pivot and othre frequency rules that
provided that valid union can fit into that union regulatory
rule by computing an intersection. If an intersection is
possible it means two rules can be optimized out. We do
this repetitively.

Note: cfg80211's nl80211.h API has:

      #define NL80211_MAX_SUPP_REG_RULES              32

Our tools, both the stream parser and the optimizer are not
limited to these artificial limits ! We can work on extending
the kernel's limit but so far we have had no needs. A few
notes below though on the existing reasoning for the limit
and possible future enhancements.

This is used nl80211_set_reg() upon intercept of a regulatory
domain being sent from userspace to it. We picked a limitation
to at least have a stopping gap to avoid userpace flooding the
kernel with a denial of service requests on memory from userspace.
This means that userspace can only request at most a kmalloc
of up to 32 regulatory rules for processing for the regulatory
data that we are copying from userspace. There's a Linux kernel
enhancement that will be made soon so that we invalidate bogus
requests, by checking to see if the incomming regulatory domain
alpha2 was not expected upon a regulatory hint initiator (even
if userspace first tells the kernel it is waiting for a response
from kernel space), and if its invalid then we drop the userspace
supplied request, therefore avoiding some form of flooding on
memory to the kernel.

Note that we can still get flooding if the userspace API is used
to *request* to the kernel for a regulatory domain to be sent
from userspace, in that case the kernel will properly expect the
regulatory data for the alpha2. To prevent flooding there perhaps
its a good idea for us to check whether a userspace pending request
is pendingg and if so deny new updates until the last one triggers
a timeout.

Screenshot for a US file with 40 rules:

mcgrof@frijol ~/devel/xlreg (git::master)$ cat us | grep --"(" | wc -l
40

mcgrof@frijol ~/devel/crda (git::master)$ cat us
country US: DFS-FCC
        (2402.000 - 2422.000 @ 20.000), (30.00)
        (2407.000 - 2427.000 @ 20.000), (30.00)
        (2412.000 - 2432.000 @ 20.000), (30.00)
        (2417.000 - 2437.000 @ 20.000), (30.00)
        (2422.000 - 2442.000 @ 20.000), (30.00)
        (2427.000 - 2447.000 @ 20.000), (30.00)
        (2432.000 - 2452.000 @ 20.000), (30.00)
        (2437.000 - 2457.000 @ 20.000), (30.00)
        (2442.000 - 2462.000 @ 20.000), (30.00)
        (2447.000 - 2467.000 @ 20.000), (30.00)
        (2452.000 - 2472.000 @ 20.000), (30.00)
        (2402.000 - 2442.000 @ 40.000), (30.00)
        (2407.000 - 2447.000 @ 40.000), (30.00)
        (2412.000 - 2452.000 @ 40.000), (30.00)
        (2417.000 - 2457.000 @ 40.000), (30.00)
        (2422.000 - 2462.000 @ 40.000), (30.00)
        (2427.000 - 2467.000 @ 40.000), (30.00)
        (2432.000 - 2472.000 @ 40.000), (30.00)
        (5170.000 - 5190.000 @ 20.000), (17.00)
        (5190.000 - 5210.000 @ 20.000), (17.00)
        (5210.000 - 5230.000 @ 20.000), (17.00)
        (5230.000 - 5250.000 @ 20.000), (17.00)
        (5250.000 - 5270.000 @ 20.000), (23.00), DFS
        (5270.000 - 5290.000 @ 20.000), (23.00), DFS
        (5290.000 - 5310.000 @ 20.000), (23.00), DFS
        (5310.000 - 5330.000 @ 20.000), (23.00), DFS
        (5735.000 - 5755.000 @ 20.000), (30.00)
        (5755.000 - 5775.000 @ 20.000), (30.00)
        (5775.000 - 5795.000 @ 20.000), (30.00)
        (5795.000 - 5815.000 @ 20.000), (30.00)
        (5815.000 - 5835.000 @ 20.000), (30.00)
        (5170.000 - 5210.000 @ 40.000), (17.00)
        (5210.000 - 5250.000 @ 40.000), (17.00)
        (5250.000 - 5290.000 @ 40.000), (23.00), DFS
        (5290.000 - 5330.000 @ 40.000), (23.00), DFS
        (5735.000 - 5775.000 @ 40.000), (30.00)
        (5775.000 - 5815.000 @ 40.000), (30.00)
        (5170.000 - 5250.000 @ 80.000), (17.00)
        (5250.000 - 5330.000 @ 80.000), (23.00), DFS
        (5735.000 - 5815.000 @ 80.000), (30.00)

mcgrof@frijol ~/devel/crda (git::master)$ cat us | ./optimize
country US: DFS-FCC
        (2402.000 - 2472.000 @ 40.000), (30.00)
        (5170.000 - 5250.000 @ 80.000), (17.00)
        (5250.000 - 5330.000 @ 80.000), (23.00), DFS
        (5735.000 - 5835.000 @ 80.000), (30.00)

I've also tested this with the current db.txt from wireless-regdb
and get real optimiziations which I will post later.

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 Makefile   |   8 +-
 optimize.c |  40 +++++++++
 reglib.c   | 300 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 reglib.h   |  16 ++++
 4 files changed, 360 insertions(+), 4 deletions(-)
 create mode 100644 optimize.c

diff --git a/Makefile b/Makefile
index bd9c220..9e37ccd 100644
--- a/Makefile
+++ b/Makefile
@@ -28,7 +28,7 @@ LDLIBS += -lm
 
 all: all_noverify verify
 
-all_noverify: crda intersect regdbdump db2rd
+all_noverify: crda intersect regdbdump db2rd optimize
 
 ifeq ($(USE_OPENSSL),1)
 CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl`
@@ -126,6 +126,10 @@ db2rd: reglib.o db2rd.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
+optimize: reglib.o optimize.o
+	$(NQ) '  LD  ' $@
+	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
+
 verify: $(REG_BIN) regdbdump
 	$(NQ) '  CHK  $(REG_BIN)'
 	$(Q)./regdbdump $(REG_BIN) >/dev/null
@@ -157,6 +161,6 @@ install: crda crda.8.gz regdbdump.8.gz
 	$(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz
 
 clean:
-	$(Q)rm -f crda regdbdump intersect db2rd \
+	$(Q)rm -f crda regdbdump intersect db2rd optimize \
 		*.o *~ *.pyc keys-*.c *.gz \
 	udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
diff --git a/optimize.c b/optimize.c
new file mode 100644
index 0000000..89d714b
--- /dev/null
+++ b/optimize.c
@@ -0,0 +1,40 @@
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <arpa/inet.h> /* ntohl */
+#include <string.h>
+
+#include "nl80211.h"
+#include "reglib.h"
+
+int main(int argc, char **argv)
+{
+	struct ieee80211_regdomain *rd = NULL, *rd_opt = NULL;
+	FILE *fp;
+
+	if (argc != 1) {
+		fprintf(stderr, "Usage: cat db.txt | %s\n", argv[0]);
+		return -EINVAL;
+	}
+
+	fp = reglib_create_parse_stream(stdin);
+	if (!fp)
+		return -EINVAL;
+
+	reglib_for_each_country_stream(fp, rd) {
+		rd_opt = reglib_optimize_regdom(rd);
+		if (!rd_opt){
+			fprintf(stderr, "Unable to optimize %c%c\n",
+				rd->alpha2[0],
+				rd->alpha2[1]);
+			free(rd);
+			continue;
+		}
+		reglib_print_regdom(rd_opt);
+		free(rd);
+		free(rd_opt);
+	}
+
+	fclose(fp);
+	return 0;
+}
diff --git a/reglib.c b/reglib.c
index 6191acd..9577ada 100644
--- a/reglib.c
+++ b/reglib.c
@@ -459,6 +459,49 @@ int reglib_is_valid_rd(const struct ieee80211_regdomain *rd)
 	return 1;
 }
 
+static int reg_rules_union(const struct ieee80211_reg_rule *rule1,
+			   const struct ieee80211_reg_rule *rule2,
+			   struct ieee80211_reg_rule *union_rule)
+{
+	const struct ieee80211_freq_range *freq_range1, *freq_range2;
+	struct ieee80211_freq_range *freq_range;
+	const struct ieee80211_power_rule *power_rule1, *power_rule2;
+	struct ieee80211_power_rule *power_rule;
+
+	freq_range1 = &rule1->freq_range;
+	freq_range2 = &rule2->freq_range;
+	freq_range = &union_rule->freq_range;
+
+	power_rule1 = &rule1->power_rule;
+	power_rule2 = &rule2->power_rule;
+	power_rule = &union_rule->power_rule;
+
+
+	if (freq_range1->end_freq_khz < freq_range2->start_freq_khz)
+		return -EINVAL;
+	if (freq_range2->end_freq_khz < freq_range1->start_freq_khz)
+		return -EINVAL;
+
+	freq_range->start_freq_khz = reglib_min(freq_range1->start_freq_khz,
+					 freq_range2->start_freq_khz);
+	freq_range->end_freq_khz = reglib_max(freq_range1->end_freq_khz,
+				       freq_range2->end_freq_khz);
+	freq_range->max_bandwidth_khz = reglib_max(freq_range1->max_bandwidth_khz,
+					    freq_range2->max_bandwidth_khz);
+
+	power_rule->max_eirp = reglib_max(power_rule1->max_eirp,
+		power_rule2->max_eirp);
+	power_rule->max_antenna_gain = reglib_max(power_rule1->max_antenna_gain,
+		power_rule2->max_antenna_gain);
+
+	union_rule->flags = rule1->flags | rule2->flags;
+
+	if (!is_valid_reg_rule(union_rule))
+		return -EINVAL;
+
+	return 0;
+}
+
 /*
  * Helper for reglib_intersect_rds(), this does the real
  * mathematical intersection fun
@@ -971,8 +1014,10 @@ static int reglib_parse_rule(FILE *fp, struct ieee80211_reg_rule *reg_rule)
 
 	memset(line, 0, sizeof(line));
 	line_p = fgets(line, sizeof(line), fp);
-	if (line_p != line)
+	if (line_p != line) {
+		free(reglib_rule_parsers);
 		return -EINVAL;
+	}
 
 	for (i = 0; i < reglib_rule_parsers->n_parsers; i++) {
 		r = reglib_rule_parsers->rule_parsers[i](line, reg_rule);
@@ -980,6 +1025,8 @@ static int reglib_parse_rule(FILE *fp, struct ieee80211_reg_rule *reg_rule)
 			break;
 	}
 
+	free(reglib_rule_parsers);
+
 	return r;
 }
 
@@ -1151,8 +1198,10 @@ struct ieee80211_regdomain *__reglib_parse_country(FILE *fp)
 
 	line_p = fgets(line, sizeof(line), fp);
 
-	if (line_p != line)
+	if (line_p != line) {
+		free(reglib_country_parsers);
 		return NULL;
+	}
 
 	for (i = 0; i < reglib_country_parsers->n_parsers; i++) {
 		r = reglib_country_parsers->country_parsers[i](line, &tmp_rd);
@@ -1162,11 +1211,14 @@ struct ieee80211_regdomain *__reglib_parse_country(FILE *fp)
 
 	if (r != 0) {
 		fprintf(stderr, "Invalid country line: %s", line);
+		free(reglib_country_parsers);
 		return NULL;
 	}
 
 	rd = reglib_parse_rules(fp, &tmp_rd);
 
+	free(reglib_country_parsers);
+
 	return rd;
 }
 
@@ -1250,3 +1302,247 @@ FILE *reglib_create_parse_stream(FILE *f)
 
 	return fp;
 }
+
+/*
+ * Just whatever for now, nothing formal, but note that as bands
+ * grow we'll want to make this a bit more formal somehow.
+ */
+static uint32_t reglib_deduce_band(uint32_t start_freq_khz)
+{
+	uint32_t freq_mhz = REGLIB_KHZ_TO_MHZ(start_freq_khz);
+
+	if (freq_mhz >= 4000)
+		return 5;
+	if (freq_mhz > 2000 && freq_mhz < 4000)
+		return 2;
+	if (freq_mhz > 50000)
+		return 60;
+	return 1234;
+}
+
+/*
+ * The idea behind a rule key is that if two rule keys share the
+ * same key they can be merged together if their frequencies overlap.
+ */
+static uint64_t reglib_rule_key(struct ieee80211_reg_rule *reg_rule)
+{
+	struct ieee80211_power_rule *power_rule;
+	struct ieee80211_freq_range *freq_range;
+	uint32_t band;
+	uint32_t key;
+
+	freq_range = &reg_rule->freq_range;
+	band = reglib_deduce_band(freq_range->start_freq_khz);
+
+	power_rule = &reg_rule->power_rule;
+
+	key = ((power_rule->max_eirp ^  0) <<  0) ^
+	      ((reg_rule->flags      ^  8) <<  8) ^
+	      ((band                 ^ 16) << 16);
+
+	return key;
+}
+
+struct reglib_optimize_map {
+	bool optimized;
+	uint32_t key;
+};
+
+/* Does the provided rule suffice both of the other two */
+static int reglib_opt_rule_fit(struct ieee80211_reg_rule *rule1,
+			       struct ieee80211_reg_rule *rule2,
+			       struct ieee80211_reg_rule *opt_rule)
+{
+	struct ieee80211_reg_rule interesected_rule;
+	struct ieee80211_reg_rule *int_rule;
+	int r;
+
+	memset(&interesected_rule, 0, sizeof(struct ieee80211_reg_rule));
+	int_rule = &interesected_rule;
+
+	r = reg_rules_intersect(rule1, opt_rule, int_rule);
+	if (r != 0)
+		return r;
+	r = reg_rules_intersect(rule2, opt_rule, int_rule);
+	if (r != 0)
+		return r;
+
+	return 0;
+}
+
+static int reg_rule_optimize(struct ieee80211_reg_rule *rule1,
+			     struct ieee80211_reg_rule *rule2,
+			     struct ieee80211_reg_rule *opt_rule)
+{
+	int r;
+
+	r = reg_rules_union(rule1, rule2, opt_rule);
+	if (r != 0)
+		return r;
+	r = reglib_opt_rule_fit(rule1, rule2, opt_rule);
+	if (r != 0)
+		return r;
+
+	return 0;
+}
+
+/*
+ * Here's the math explanation:
+ *
+ * This takes each pivot frequency on the regulatory domain, computes
+ * the union between it each regulatory rule on the regulatory domain
+ * sequentially, and after that it tries to verify that the pivot frequency
+ * fits on it by computing an intersection between it and the union, if
+ * a rule exist as a possible intersection then we know the rule can be
+ * subset of the combination of the two frequency ranges (union) computed.
+ */
+static unsigned int reg_rule_optimize_rd(struct ieee80211_regdomain *rd,
+					 unsigned int rule_idx,
+					 struct ieee80211_reg_rule *opt_rule,
+					 struct reglib_optimize_map *opt_map)
+{
+	unsigned int i;
+	struct ieee80211_reg_rule *rule1;
+	struct ieee80211_reg_rule *rule2;
+
+	struct ieee80211_reg_rule tmp_optimized_rule;
+	struct ieee80211_reg_rule *tmp_opt_rule;
+
+	struct ieee80211_reg_rule *target_rule;
+
+	unsigned int optimized = 0;
+	int r;
+
+	if (rule_idx > rd->n_reg_rules)
+		return 0;
+
+	rule1 = &rd->reg_rules[rule_idx];
+
+	memset(&tmp_optimized_rule, 0, sizeof(struct ieee80211_reg_rule));
+	tmp_opt_rule = &tmp_optimized_rule;
+
+	memset(opt_rule, 0, sizeof(*opt_rule));
+
+	for (i = 0; i < rd->n_reg_rules; i++) {
+		if (rule_idx == i)
+			continue;
+		rule2 = &rd->reg_rules[i];
+		if (opt_map[rule_idx].key != opt_map[i].key)
+			continue;
+
+		target_rule = optimized ? opt_rule : rule1;
+		r = reg_rule_optimize(target_rule, rule2, tmp_opt_rule);
+		if (r != 0)
+			continue;
+		memcpy(opt_rule, tmp_opt_rule, sizeof(*tmp_opt_rule));
+
+		if (!opt_map[i].optimized) {
+			opt_map[i].optimized = true;
+			optimized++;
+		}
+		if (!opt_map[rule_idx].optimized) {
+			opt_map[rule_idx].optimized = true;
+			optimized++;
+		}
+	}
+	return optimized;
+}
+
+struct ieee80211_regdomain *
+reglib_optimize_regdom(struct ieee80211_regdomain *rd)
+{
+	struct ieee80211_regdomain *opt_rd = NULL;
+	struct ieee80211_reg_rule *reg_rule;
+	struct ieee80211_reg_rule *reg_rule_dst;
+	struct ieee80211_reg_rule optimized_reg_rule;
+	struct ieee80211_reg_rule *opt_reg_rule;
+	struct reglib_optimize_map *opt_map;
+	unsigned int i, idx = 0, non_opt = 0, opt = 0;
+	size_t num_rules, size_of_regd, size_of_opt_map;
+	unsigned int num_opts = 0;
+
+	size_of_opt_map = (rd->n_reg_rules + 2) *
+		sizeof(struct reglib_optimize_map);
+	opt_map = malloc(size_of_opt_map);
+	if (!opt_map)
+		return NULL;
+
+	memset(opt_map, 0, size_of_opt_map);
+	memset(&optimized_reg_rule, 0, sizeof(struct ieee80211_reg_rule));
+
+	opt_reg_rule = &optimized_reg_rule;
+
+	for (i = 0; i < rd->n_reg_rules; i++) {
+		reg_rule = &rd->reg_rules[i];
+		opt_map[i].key = reglib_rule_key(reg_rule);
+	}
+	for (i = 0; i < rd->n_reg_rules; i++) {
+		reg_rule = &rd->reg_rules[i];
+		if (opt_map[i].optimized)
+			continue;
+		num_opts = reg_rule_optimize_rd(rd, i, opt_reg_rule, opt_map);
+		if (!num_opts)
+			non_opt++;
+		else
+			opt += (num_opts ? 1 : 0);
+	}
+
+	num_rules = non_opt + opt;
+
+	if (num_rules > rd->n_reg_rules)
+		goto fail_opt_map;
+
+	size_of_regd = reglib_array_len(sizeof(struct ieee80211_regdomain),
+					num_rules + 1,
+					sizeof(struct ieee80211_reg_rule));
+
+	opt_rd = malloc(size_of_regd);
+	if (!opt_rd)
+		goto fail_opt_map;
+	memset(opt_rd, 0, size_of_regd);
+
+	opt_rd->n_reg_rules = num_rules;
+	opt_rd->alpha2[0] = rd->alpha2[0];
+	opt_rd->alpha2[1] = rd->alpha2[1];
+	opt_rd->dfs_region = rd->dfs_region;
+
+	memset(opt_map, 0, size_of_opt_map);
+	memset(&optimized_reg_rule, 0, sizeof(struct ieee80211_reg_rule));
+
+	opt_reg_rule = &optimized_reg_rule;
+
+	for (i = 0; i < rd->n_reg_rules; i++) {
+		reg_rule = &rd->reg_rules[i];
+		opt_map[i].key = reglib_rule_key(reg_rule);
+	}
+
+	for (i = 0; i < rd->n_reg_rules; i++) {
+		reg_rule = &rd->reg_rules[i];
+		reg_rule_dst = &opt_rd->reg_rules[idx];
+		if (opt_map[i].optimized)
+			continue;
+		num_opts = reg_rule_optimize_rd(rd, i, opt_reg_rule, opt_map);
+		if (!num_opts)
+			memcpy(reg_rule_dst, reg_rule, sizeof(struct ieee80211_reg_rule));
+		else
+			memcpy(reg_rule_dst, opt_reg_rule, sizeof(struct ieee80211_reg_rule));
+		idx++;
+	}
+
+	if (idx != num_rules)
+		goto fail;
+
+	for (i = 0; i < opt_rd->n_reg_rules; i++) {
+		reg_rule = &opt_rd->reg_rules[i];
+		if (!is_valid_reg_rule(reg_rule))
+			goto fail;
+	}
+
+	free(opt_map);
+	return opt_rd;
+fail:
+	free(opt_rd);
+fail_opt_map:
+	free(opt_map);
+	return NULL;
+}
diff --git a/reglib.h b/reglib.h
index 885792e..d570c36 100644
--- a/reglib.h
+++ b/reglib.h
@@ -219,6 +219,22 @@ FILE *reglib_create_parse_stream(FILE *fp);
  */
 struct ieee80211_regdomain *reglib_parse_country(FILE *fp);
 
+/**
+ * @reglib_optimize_regdom - optimize a regulatory domain
+ *
+ * @rd: a regulatory domain to be optimized
+ *
+ * A regulatory domain may exist without optimal expressions
+ * over its rules. This will look for regulatory rules that can
+ * be combined together to reduce the size of the regulatory
+ * domain and its expression.
+ *
+ * Regulatory rules will be combined if their max allowed
+ * bandwidth, max EIRP, and flags all match.
+ */
+struct ieee80211_regdomain *
+reglib_optimize_regdom(struct ieee80211_regdomain *rd);
+
 #define reglib_for_each_country_stream(__fp, __rd)		\
 	for (__rd = reglib_parse_country(__fp);			\
 	     __rd != NULL;					\
-- 
1.8.4.rc3

[PATCH v2 5/6] crda: make ssl keys include stdint.h

[Luis R. Rodriguez]

This is required to fix compilation if we
move reglig to its own library.

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 utils/key2pub.py | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/utils/key2pub.py b/utils/key2pub.py
index 4d85369..3e84cd2 100755
--- a/utils/key2pub.py
+++ b/utils/key2pub.py
@@ -59,6 +59,7 @@ def print_ssl_32(output, name, val):
 
 def print_ssl(output, name, val):
     import struct
+    output.write('#include <stdint.h>\n')
     if len(struct.pack('@L', 0)) == 8:
         return print_ssl_64(output, name, val)
     else:
@@ -85,6 +86,7 @@ static struct pubkey keys[] = {
     pass
 
 def print_gcrypt(output, name, val):
+    output.write('#include <stdint.h>\n')
     while val[0] == '\0':
         val = val[1:]
     output.write('static const uint8_t %s[%d] = {\n' % (name, len(val)))
-- 
1.8.4.rc3

[PATCH v2 6/6] crda: make reglib a shared library

[Luis R. Rodriguez]

Now that we have quite a few helpers this puts the more
valuable helpers into a library.

Signed-off-by: Luis R. Rodriguez <mcgrof@do-not-panic.com>
---
 Makefile | 48 ++++++++++++++++++++++++++++++++++++------------
 1 file changed, 36 insertions(+), 12 deletions(-)

diff --git a/Makefile b/Makefile
index 9e37ccd..4a351c6 100644
--- a/Makefile
+++ b/Makefile
@@ -5,6 +5,8 @@ REG_GIT?=git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-regdb.g
 
 PREFIX ?= /usr/
 MANDIR ?= $(PREFIX)/share/man/
+INCLUDE_DIR ?= $(PREFIX)/include/reglib/
+LIBDIR ?= $(PREFIX)/lib
 
 SBINDIR ?= /sbin/
 
@@ -23,24 +25,29 @@ UDEV_RULE_DIR?=/lib/udev/rules.d/
 PUBKEY_DIR?=pubkeys
 RUNTIME_PUBKEY_DIR?=/etc/wireless-regdb/pubkeys
 
+CFLAGS += -O2 -fpic
+CFLAGS += -std=gnu99 -Wall -Werror -pedantic
 CFLAGS += -Wall -g
 LDLIBS += -lm
+LDLIBREG += -lreg
+LIBREG += libreg.so
+LDFLAGS += -L ./ $(LDLIBREG)
 
 all: all_noverify verify
 
-all_noverify: crda intersect regdbdump db2rd optimize
+all_noverify: $(LIBREG) crda intersect regdbdump db2rd optimize
 
 ifeq ($(USE_OPENSSL),1)
 CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl`
 LDLIBS += `pkg-config --libs openssl`
 
-reglib.o: keys-ssl.c
+$(LIBREG): keys-ssl.c
 
 else
 CFLAGS += -DUSE_GCRYPT
 LDLIBS += -lgcrypt
 
-reglib.o: keys-gcrypt.c
+$(LIBREG): keys-gcrypt.c
 
 endif
 MKDIR ?= mkdir -p
@@ -106,39 +113,56 @@ keys-%.c: utils/key2pub.py $(wildcard $(PUBKEY_DIR)/*.pem)
 	$(NQ) '  Trusted pubkeys:' $(wildcard $(PUBKEY_DIR)/*.pem)
 	$(Q)./utils/key2pub.py --$* $(wildcard $(PUBKEY_DIR)/*.pem) $@
 
-%.o: %.c regdb.h reglib.h
+$(LIBREG): regdb.h reglib.h reglib.c
+	$(NQ) '  CC  ' $@
+	$(Q)$(CC) $(CFLAGS) $(CPPFLAGS) -o $@ -shared -Wl,-soname,$(LIBREG) $^
+
+install-libreg-headers:
+	$(NQ) '  INSTALL  libreg-headers'
+	$(Q)mkdir -p $(INCLUDE_DIR)
+	$(Q)cp *.h $(INCLUDE_DIR)/
+
+install-libreg:
+	$(NQ) '  INSTALL  libreg'
+	$(Q)mkdir -p $(LIBDIR)
+	$(Q)cp $(LIBREG) $(LIBDIR)/
+	$(Q)ldconfig
+
+%.o: %.c regdb.h $(LIBREG)
 	$(NQ) '  CC  ' $@
 	$(Q)$(CC) -c $(CPPFLAGS) $(CFLAGS) -o $@ $<
 
-crda: reglib.o crda.o
+crda: crda.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) $(NLLIBS)
 
-regdbdump: reglib.o regdbdump.o
+regdbdump: regdbdump.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
-intersect: reglib.o intersect.o
+intersect: intersect.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
-db2rd: reglib.o db2rd.o
+db2rd: db2rd.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
-optimize: reglib.o optimize.o
+optimize: optimize.o
 	$(NQ) '  LD  ' $@
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS)
 
 verify: $(REG_BIN) regdbdump
 	$(NQ) '  CHK  $(REG_BIN)'
-	$(Q)./regdbdump $(REG_BIN) >/dev/null
+	$(Q)\
+		LD_LIBRARY_PATH=.:$(LD_LIBRARY_PATH) \
+		./regdbdump $(REG_BIN) >/dev/null
 
 %.gz: %
 	@$(NQ) ' GZIP' $<
 	$(Q)gzip < $< > $@
 
-install: crda crda.8.gz regdbdump.8.gz
+install: install-libreg install-libreg-headers crda crda.8.gz regdbdump.8.gz
 	$(NQ) '  INSTALL  crda'
 	$(Q)$(MKDIR) $(DESTDIR)/$(SBINDIR)
 	$(Q)$(INSTALL) -m 755 -t $(DESTDIR)/$(SBINDIR) crda
@@ -161,6 +185,6 @@ install: crda crda.8.gz regdbdump.8.gz
 	$(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz
 
 clean:
-	$(Q)rm -f crda regdbdump intersect db2rd optimize \
+	$(Q)rm -f $(LIBREG) crda regdbdump intersect db2rd optimize \
 		*.o *~ *.pyc keys-*.c *.gz \
 	udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
-- 
1.8.4.rc3