This took quite a bit longer than I expected, but I have finally
finished my BIP 21 URI parser. I am attaching several patches for your
review. If these look good, I will submit a pull request.

The first patch, 0001-Implement-a-bitcoin-URI-parser, adds the parser
to libwallet. The other two patches tighten up the base58 decoding in
libbitcoin.

I have given my best effort towards following the libbitcoin style. My
background is in writing embedded C code for tiny micro-controllers,
but I have tried to leave those habits behind and code in an idiomatic
C++11 manner. Hopefully the code is clean enough for your standards.

-William
From edd0420c81991a7984adb317e46d0b9f11705b0a Mon Sep 17 00:00:00 2001
From: William Swanson <swansontec@???>
Date: Tue, 11 Mar 2014 00:52:16 -0700
Subject: [PATCH] Implement a bitcoin URI parser

This parser follows the BIP 21 standard as closely as possible.
---
 AUTHORS                    |   3 +
 examples/.gitignore        |   2 +
 examples/Makefile          |   9 +-
 examples/uri.cpp           | 105 ++++++++++++++++++++++
 include/wallet/Makefile.am |   3 +-
 include/wallet/uri.hpp     |  72 +++++++++++++++
 include/wallet/wallet.hpp  |   1 +
 src/Makefile.am            |   3 +-
 src/uri.cpp                | 212 +++++++++++++++++++++++++++++++++++++++++++++
 9 files changed, 405 insertions(+), 5 deletions(-)
 create mode 100644 examples/.gitignore
 create mode 100644 examples/uri.cpp
 create mode 100644 include/wallet/uri.hpp
 create mode 100644 src/uri.cpp

diff --git a/AUTHORS b/AUTHORS
index e9fa421..c9ca425 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -13,6 +13,9 @@ Authors:
* Denis Roio (jaromil)
Hosting.

+* William Swanson
+ Development. Added URI code.
+
Thanks:

Kamil Domański (kdomanski)
diff --git a/examples/.gitignore b/examples/.gitignore
new file mode 100644
index 0000000..c91bfb6
--- /dev/null
+++ b/examples/.gitignore
@@ -0,0 +1,2 @@
+determ
+uri
diff --git a/examples/Makefile b/examples/Makefile
index 17c56de..2dcd229 100644
--- a/examples/Makefile
+++ b/examples/Makefile
@@ -3,14 +3,17 @@ LIBS=$(shell pkg-config --libs libbitcoin libwallet)

default: all

-determ.o: determ.cpp
+.cpp.o:
     $(CXX) -o $@ -c $< $(CXXFLAGS)

 determ: determ.o
     $(CXX) -o $@ $< $(LIBS)

-all: determ
+uri: uri.o
+    $(CXX) -o $@ $< $(LIBS)
+
+all: determ uri

 clean:
-    rm -f determ
+    rm -f determ uri
     rm -f *.o
diff --git a/examples/uri.cpp b/examples/uri.cpp
new file mode 100644
index 0000000..e5d881f
--- /dev/null
+++ b/examples/uri.cpp
@@ -0,0 +1,105 @@
+/*
+ * Copyright (c) 2011-2013 libwallet developers (see AUTHORS)
+ *
+ * This file is part of libwallet.
+ *
+ * libwallet is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License with
+ * additional permissions to the one published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option)
+ * any later version. For more information see LICENSE.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+/*
+  Demonstration of URI utilities.
+*/
+#include <bitcoin/bitcoin.hpp>
+#include <wallet/wallet.hpp>
+#include <iostream>
+
+void test_uri_parse(std::string uri)
+{
+    std::cout << "parse URI: \"" << uri << "\"" << std::endl;
+    class parse_handler: public libwallet::uri_parse_handler
+    {
+        virtual void got_address(std::string address)
+        {
+            std::cout << "    got address: \"" << address << "\"" << std::endl;
+        }
+        virtual void got_param(std::string key, std::string value)
+        {
+            std::cout << "    got parameter: \"" << key << "\" = \"" <<
+                value << "\"" << std::endl;
+        }
+    } handler;
+    if (libwallet::uri_parse(uri, handler))
+        std::cout << "    ok" << std::endl;
+    else
+        std::cout << "    error" << std::endl;
+}
+
+void test_uri_decode(std::string uri)
+{
+    libwallet::decoded_uri out = libwallet::uri_decode(uri);
+    std::cout << "decode URI: \"" << uri << "\"" << std::endl;
+    if (!out.valid)
+        std::cout << "    invalid" << std::endl;
+    if (out.has_address)
+        std::cout << "    address: " << out.address.encoded() << std::endl;
+    if (out.has_amount)
+        std::cout << "    amount: " << out.amount << std::endl;
+    if (out.has_label)
+        std::cout << "    label: \"" << out.label << "\"" << std::endl;
+    if (out.has_message)
+        std::cout << "    message: \"" << out.message << "\"" << std::endl;
+    if (out.has_r)
+        std::cout << "    r: \"" << out.r << "\"" << std::endl;
+}
+
+int main()
+{
+    test_uri_parse("bitcoin:113Pfw4sFqN1T5kXUnKbqZHMJHN9oyjtgD?label=test");
+    test_uri_parse("bitcoin:");
+    test_uri_parse("bitcorn:");
+    test_uri_parse("BITCOIN:?");
+    test_uri_parse("Bitcoin:?&");
+    test_uri_parse("bitcOin:&");
+    test_uri_parse("bitcoin:?x=y");
+    test_uri_parse("bitcoin:?x=");
+    test_uri_parse("bitcoin:?=y");
+    test_uri_parse("bitcoin:?=");
+    test_uri_parse("bitcoin:?x");
+    test_uri_parse("bitcoin:19z88");
+    test_uri_parse("bitcoin:19l88");
+    test_uri_parse("bitcoin:19z88?x=http://www.example.com?purchase%3Dshoes");
+    test_uri_parse("bitcoin:19z88?name=%E3%83%95"); // UTF-8
+    test_uri_parse("bitcoin:19z88?name=%3");
+    test_uri_parse("bitcoin:19z88?name=%3G");
+    test_uri_parse("bitcoin:19z88?name=%3f");
+    test_uri_parse("bitcoin:%31");
+
+    std::cout << "================================" << std::endl;
+
+    test_uri_decode("bitcoin:113Pfw4sFqN1T5kXUnKbqZHMJHN9oyjtgD");
+    test_uri_decode("bitcoin:19z88");
+    test_uri_decode("bitcoin:?=");
+    test_uri_decode("bitcoin:?amount=4.2");
+    test_uri_decode("bitcoin:?amount=.");
+    test_uri_decode("bitcoin:?amount=4.2.4");
+    test_uri_decode("bitcoin:?amount=foo");
+    test_uri_decode("bitcoin:?label=Bob");
+    test_uri_decode("bitcoin:?message=Hi%20Alice");
+    test_uri_decode("bitcoin:?r=http://www.example.com?purchase%3Dshoes");
+    test_uri_decode("bitcoin:?foo=ignore");
+    test_uri_decode("bitcoin:?req-foo=die");
+
+    return 0;
+}
+
diff --git a/include/wallet/Makefile.am b/include/wallet/Makefile.am
index 748eed4..94eca86 100644
--- a/include/wallet/Makefile.am
+++ b/include/wallet/Makefile.am
@@ -4,5 +4,6 @@ wallet_include_HEADERS = \
     key_formats.hpp \
     transaction.hpp \
     deterministic_wallet.hpp \
-    mnemonic.hpp
+    mnemonic.hpp \
+    uri.hpp

diff --git a/include/wallet/uri.hpp b/include/wallet/uri.hpp
new file mode 100644
index 0000000..959d02b
--- /dev/null
+++ b/include/wallet/uri.hpp
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2011-2013 libwallet developers (see AUTHORS)
+ *
+ * This file is part of libwallet.
+ *
+ * libwallet is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License with
+ * additional permissions to the one published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option)
+ * any later version. For more information see LICENSE.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef LIBWALLET_URI_HPP
+#define LIBWALLET_URI_HPP
+
+#include <bitcoin/address.hpp>
+
+namespace libwallet {
+
+struct uri_parse_handler {
+    virtual void got_address(std::string address) = 0;
+    virtual void got_param(std::string key, std::string value) = 0;
+};
+
+bool uri_parse(const std::string& uri, uri_parse_handler& handler);
+bool uri_validate(const std::string& uri);
+
+/**
+ * A decoded bitcoin URI corresponding to BIP 21 and BIP 72.
+ * All string members are UTF-8.
+ */
+struct decoded_uri
+{
+    bool valid;
+    bool has_address;
+    bool has_amount;
+    bool has_label;
+    bool has_message;
+    bool has_r;
+
+    libbitcoin::payment_address address;
+    uint64_t amount;
+    std::string label;
+    std::string message;
+    std::string r;
+
+    decoded_uri()
+      : valid(true), has_address(false), has_amount(false),
+        has_label(false), has_message(false), has_r(false)
+    {}
+};
+
+decoded_uri uri_decode(const std::string& uri);
+
+/**
+ * Parses a bitcoin amount string.
+ * @return string value, in satoshis, or -1 for failure.
+ */
+uint64_t parse_amount(const std::string& amount);
+
+} // libwallet
+
+#endif
+
diff --git a/include/wallet/wallet.hpp b/include/wallet/wallet.hpp
index ba88126..5829532 100644
--- a/include/wallet/wallet.hpp
+++ b/include/wallet/wallet.hpp
@@ -25,6 +25,7 @@
 #include <wallet/mnemonic.hpp>
 #include <wallet/key_formats.hpp>
 #include <wallet/transaction.hpp>
+#include <wallet/uri.hpp>

#endif

diff --git a/src/Makefile.am b/src/Makefile.am
index 835513c..2225a9c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -6,7 +6,8 @@ libwallet_la_SOURCES = \
     deterministic_wallet.cpp \
     mnemonic.cpp \
     transaction.cpp \
-    key_formats.cpp
+    key_formats.cpp \
+    uri.cpp

libwallet_la_LIBADD = $(libbitcoin_LIBS)

diff --git a/src/uri.cpp b/src/uri.cpp
new file mode 100644
index 0000000..3abce6b
--- /dev/null
+++ b/src/uri.cpp
@@ -0,0 +1,212 @@
+/*
+ * Copyright (c) 2011-2013 libwallet developers (see AUTHORS)
+ *
+ * This file is part of libwallet.
+ *
+ * libwallet is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License with
+ * additional permissions to the one published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option)
+ * any later version. For more information see LICENSE.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+#include <wallet/uri.hpp>
+#include <bitcoin/utility/base58.hpp>
+#include <sstream>
+#include <stdlib.h>
+
+namespace libwallet {
+
+static bool is_digit(char c)
+{
+    return '0' <= c && c <= '9';
+}
+static bool is_hex(char c)
+{
+    return is_digit(c) || ('A' <= c && c <= 'F') || ('a' <= c && c <= 'f');
+}
+static bool is_qchar(char c)
+{
+    return
+        ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || is_digit(c) ||
+        '-' == c || '.' == c || '_' == c || '~' == c || // unreserved
+        '!' == c || '$' == c || '\'' == c || '(' == c || ')' == c ||
+        '*' == c || '+' == c || ',' == c || ';' == c || // sub-delims
+        ':' == c || '@' == c || // pchar
+        '/' == c || '?' == c;   // query
+}
+
+static unsigned from_hex(char c)
+{
+    return
+        'A' <= c && c <= 'F' ? 10 + c - 'A' :
+        'a' <= c && c <= 'f' ? 10 + c - 'a' :
+        c - '0';
+}
+
+/**
+ * Unescapes a URI-encoded string while advancing the iterator.
+ * @param i set to one-past the last-read character on return.
+ */
+typedef std::string::const_iterator sci;
+static std::string unescape(sci& i, sci end, bool (*is_valid)(char))
+{
+    auto j = i;
+    size_t count = 0;
+    while (end != i && (is_valid(*i) ||
+        ('%' == *i && 2 < end - i && is_hex(i[1]) && is_hex(i[2]))))
+    {
+        ++count;
+        i += ('%' == *i ? 3 : 1);
+    }
+    std::string out;
+    out.reserve(count);
+    while (j != i)
+    {
+        out.push_back('%' == *j ? from_hex(j[1]) << 4 | from_hex(j[2]) : *j);
+        j += ('%' == *j ? 3 : 1);
+    }
+    return out;
+}
+
+bool uri_parse(const std::string& uri, uri_parse_handler& handler)
+{
+    auto i = uri.begin();
+
+    // URI scheme:
+    const char* lower = "bitcoin:";
+    const char* upper = "BITCOIN:";
+    while (*lower)
+    {
+        if (uri.end() == i || (*lower != *i && *upper != *i))
+            return false;
+        ++lower; ++upper; ++i;
+    }
+
+    // Payment address:
+    std::string address = unescape(i, uri.end(), libbitcoin::is_base58);
+    if (uri.end() != i && '?' != *i)
+        return false;
+    if (!address.empty())
+        handler.got_address(address);
+
+    // Parameters:
+    while (uri.end() != i)
+    {
+        ++i; // Consume '?' or '&'
+        std::string key = unescape(i, uri.end(), is_qchar);
+        std::string value;
+        if (uri.end() != i && '=' == *i)
+        {
+            ++i; // Consume '='
+            if (key.empty())
+                return false;
+            value = unescape(i, uri.end(), is_qchar);
+        }
+        if (uri.end() != i && '&' != *i)
+            return false;
+        if (!key.empty())
+            handler.got_param(key, value);
+    }
+    return true;
+}
+
+bool uri_validate(const std::string& uri)
+{
+    class parse_handler: public uri_parse_handler
+    {
+        virtual void got_address(std::string address)
+        {
+            (void)address;
+        }
+        virtual void got_param(std::string key, std::string value)
+        {
+            (void)key;
+            (void)value;
+        }
+    } handler;
+    return uri_parse(uri, handler);
+}
+
+decoded_uri uri_decode(const std::string& uri)
+{
+    class parse_handler: public uri_parse_handler
+    {
+    public:
+        decoded_uri wip_;
+        virtual void got_address(std::string address)
+        {
+            if (wip_.address.set_encoded(address))
+                wip_.has_address = true;
+            else
+                wip_.valid = false;
+        }
+        virtual void got_param(std::string key, std::string value)
+        {
+            if ("amount" == key)
+            {
+                wip_.amount = parse_amount(value);
+                if (static_cast<uint64_t>(-1) != wip_.amount)
+                    wip_.has_amount = true;
+                else
+                    wip_.valid = false;
+            }
+            else if ("label" == key)
+            {
+                wip_.label = value;
+                wip_.has_label = true;
+            }
+            else if ("message" == key)
+            {
+                wip_.message = value;
+                wip_.has_message = true;
+            }
+            else if ("r" == key)
+            {
+                wip_.r = value;
+                wip_.has_r = true;
+            }
+            else if (!key.compare(0, 4, "req-"))
+            {
+                wip_.valid = false;
+            }
+        }
+    } handler;
+    if (!uri_parse(uri, handler))
+        handler.wip_.valid = false;
+    return handler.wip_;
+}
+
+/**
+ * Validates an amount string according to the BIP 21 grammar.
+ */
+static bool check_amount(const std::string& amount)
+{
+    auto i = amount.begin();
+    while (amount.end() != i && is_digit(*i))
+        ++i;
+    if (amount.end() != i && '.' == *i)
+    {
+        ++i;
+        while (amount.end() != i && is_digit(*i))
+            ++i;
+    }
+    return amount.end() == i;
+}
+
+uint64_t parse_amount(const std::string& amount)
+{
+    if (!check_amount(amount))
+        return static_cast<uint64_t>(-1);
+    // This code might have numerical problems:
+    return static_cast<uint64_t>(100000000*strtod(amount.c_str(), nullptr));
+}
+
+} // namespace libwallet
-- 
1.9.0

From 1973ed73de5684ecc078a674c6170bc3ca9df77e Mon Sep 17 00:00:00 2001
From: William Swanson <swansontec@???>
Date: Wed, 5 Mar 2014 16:38:59 -0800
Subject: [PATCH 1/2] Detect wrongly-encoded bitcoin addresses

---
 include/bitcoin/utility/base58.hpp |  3 +++
 src/address.cpp                    |  2 ++
 src/utility/base58.cpp             | 13 ++++++++++++-
 3 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/include/bitcoin/utility/base58.hpp b/include/bitcoin/utility/base58.hpp
index 63e67c9..75ac9cd 100644
--- a/include/bitcoin/utility/base58.hpp
+++ b/include/bitcoin/utility/base58.hpp
@@ -24,6 +24,9 @@

namespace libbitcoin {

+bool is_base58(char c);
+bool is_base58(std::string const& text);
+
std::string encode_base58(const data_chunk& unencoded_data);

data_chunk decode_base58(std::string encoded_data);
diff --git a/src/address.cpp b/src/address.cpp
index f71607c..ab52049 100644
--- a/src/address.cpp
+++ b/src/address.cpp
@@ -59,6 +59,8 @@ const short_hash& payment_address::hash() const

 bool payment_address::set_encoded(const std::string& encoded_address)
 {
+    if (!is_base58(encoded_address))
+        return false;
     const data_chunk decoded_address = decode_base58(encoded_address);
     // version + 20 bytes short hash + 4 bytes checksum
     if (decoded_address.size() != 25)
diff --git a/src/utility/base58.cpp b/src/utility/base58.cpp
index c587e52..f31ae63 100644
--- a/src/utility/base58.cpp
+++ b/src/utility/base58.cpp
@@ -26,7 +26,18 @@ namespace libbitcoin {

// Thanks for all the wonderful bitcoin hackers

-const char* base58_chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
+const char base58_chars[] = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
+
+bool is_base58(char c)
+{
+    // This works because the base58 characters happen to be in sorted order
+    return std::binary_search(base58_chars, std::end(base58_chars) - 1, c);
+}
+bool is_base58(std::string const& text)
+{
+    return std::all_of(text.begin(), text.end(),
+        [](char c) { return is_base58(c); });
+}

 std::string encode_base58(const data_chunk& unencoded_data)
 {                                                                                
-- 
1.9.0

From 10d3c7e76bd3d9f9eae577f0acb4062f0c0ac7fe Mon Sep 17 00:00:00 2001
From: William Swanson <swansontec@???>
Date: Thu, 6 Mar 2014 16:31:38 -0800
Subject: [PATCH 2/2] Optimize the base58 decoder

The existing version was not using a binary search,
and was potentially allocating memory on each iteration.
---
src/utility/base58.cpp | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/utility/base58.cpp b/src/utility/base58.cpp
index f31ae63..a089fb9 100644
--- a/src/utility/base58.cpp
+++ b/src/utility/base58.cpp
@@ -87,8 +87,9 @@ data_chunk decode_base58(std::string encoded_data)
     for (const uint8_t current_char: encoded_data)
     {                                                                            
         bn *= 58;
-        bn += std::string(base58_chars).find(current_char);
-    }                                                                            
+        bn += std::lower_bound(base58_chars, std::end(base58_chars) - 1,
+            current_char) - base58_chars;
+    }

     // Get bignum as little endian data                                          
     data_chunk temp_data = bn.data();       
-- 
1.9.0