src/setup_payload/Base41.cpp

   1 /*
   2  *
   3  *    Copyright (c) 2020 Project CHIP Authors
   4  *
   5  *    Licensed under the Apache License, Version 2.0 (the "License");
   6  *    you may not use this file except in compliance with the License.
   7  *    You may obtain a copy of the License at
   8  *
   9  *        http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *    Unless required by applicable law or agreed to in writing, software
  12  *    distributed under the License is distributed on an "AS IS" BASIS,
  13  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *    See the License for the specific language governing permissions and
  15  *    limitations under the License.
  16  */
  17
  18 /**
  19  *    @file
  20  *      This file implements converting an array of bytes into a Base41 String and
  21  *       the reverse.
  22  *
  23  *      The encoding chosen is: treat every 2 bytes of input data as a little-endian
  24  *        uint16_t, then div and mod that into 3 base41 characters, with the least-significant
  25  *        encoding bits in the first character of the resulting string.  If an odd
  26  *        number of bytes is encoded, 2 characters are used to encode the last byte.
  27  *
  28  */
  29
  30 #include "Base41.h"
  31
  32 #include <climits>
  33
  34 namespace chip {
  35
  36 static const char codes[]        = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D',
  37                               'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
  38                               'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', ' ', '*', '+', '-', '.' };
  39 static const int kBase41ChunkLen = 3;
  40 static const int kBytesChunkLen  = 2;
  41 static const int kRadix          = sizeof(codes) / sizeof(codes[0]);
  42
  43 std::string base41Encode(const uint8_t * buf, size_t buf_len)
  44 {
  45     std::string result;
  46
  47     // eat little-endian uint16_ts from the byte array
  48     // encode as 3 base41 characters
  49
  50     while (buf_len >= kBytesChunkLen)
  51     {
  52         int value = 0;
  53         for (int i = kBytesChunkLen - 1; i >= 0; i--)
  54         {
  55             value *= 256;
  56             value += buf[i];
  57         }
  58         buf_len -= kBytesChunkLen;
  59         buf += kBytesChunkLen;
  60
  61         // This code needs to correctly convey to the decoder
  62         //  the length of data encoded, so normally emits 3 chars for
  63         //  2 bytes.
  64         // But there's a special case possible where the last
  65         //  two bytes would fit in exactly 2 chars.
  66         // The following conditions must be met:
  67         //   1. this must be the last value
  68         //   2. the value doesn't fit in a single byte, if we encode a
  69         //        small value at the end of the encoded string with a
  70         //        shortened chunk, the decoder will think only one byte
  71         //        was encoded
  72         //   3. the value can be encoded in 2 base41 chars
  73         //
  74         int encodeLen = kBase41ChunkLen;
  75         if (buf_len == 0 &&            // the very last value, i.e. not an odd byte
  76             (value > UINT8_MAX) &&     // the value wouldn't fit in one byte
  77             (value < kRadix * kRadix)) // the value can be encoded with 2 base41 chars
  78         {
  79             encodeLen--;
  80         }
  81         for (int _ = 0; _ < encodeLen; _++)
  82         {
  83             result += codes[value % kRadix];
  84             value /= kRadix;
  85         }
  86     }
  87
  88     // handle leftover bytes, if any
  89     if (buf_len != 0)
  90     {
  91         uint64_t value = 0;
  92         static_assert(sizeof(value) * CHAR_BIT >= kBytesChunkLen * 8, "value might overflow");
  93
  94         for (size_t i = buf_len; i > 0; i--)
  95         {
  96             value *= 256;
  97             value += buf[i - 1];
  98         }
  99
 100         // need to indicate there are leftover bytes, so append at least one encoding char
 101         result += codes[value % kRadix];
 102         value /= kRadix;
 103
 104         // if there's still value, encode with more chars
 105         while (value != 0)
 106         {
 107             result += codes[value % kRadix];
 108             value /= kRadix;
 109         }
 110     }
 111     return result;
 112 }
 113
 114 static inline CHIP_ERROR decodeChar(char c, uint8_t & value)
 115 {
 116     static const int kBogus = 255;
 117     // map of base41 charater to numeric value
 118     // subtract 32 from the charater, then index into this array, if possible
 119     const uint8_t decodes[] = {
 120         36,     // ' ', =32
 121         kBogus, // '!', =33
 122         kBogus, // '"', =34
 123         kBogus, // '#', =35
 124         kBogus, // '$', =36
 125         kBogus, // '%', =37
 126         kBogus, // '&', =38
 127         kBogus, // ''', =39
 128         kBogus, // '(', =40
 129         kBogus, // ')', =41
 130         37,     // '*', =42
 131         38,     // '+', =43
 132         kBogus, // ',', =44
 133         39,     // '-', =45
 134         40,     // '.', =46
 135         kBogus, // '/', =47
 136         0,      // '0', =48
 137         1,      // '1', =49
 138         2,      // '2', =50
 139         3,      // '3', =51
 140         4,      // '4', =52
 141         5,      // '5', =53
 142         6,      // '6', =54
 143         7,      // '7', =55
 144         8,      // '8', =56
 145         9,      // '9', =57
 146         kBogus, // ':', =58
 147         kBogus, // ';', =59
 148         kBogus, // '<', =50
 149         kBogus, // '=', =61
 150         kBogus, // '>', =62
 151         kBogus, // '?', =63
 152         kBogus, // '@', =64
 153         10,     // 'A', =65
 154         11,     // 'B', =66
 155         12,     // 'C', =67
 156         13,     // 'D', =68
 157         14,     // 'E', =69
 158         15,     // 'F', =70
 159         16,     // 'G', =71
 160         17,     // 'H', =72
 161         18,     // 'I', =73
 162         19,     // 'J', =74
 163         20,     // 'K', =75
 164         21,     // 'L', =76
 165         22,     // 'M', =77
 166         23,     // 'N', =78
 167         24,     // 'O', =79
 168         25,     // 'P', =80
 169         26,     // 'Q', =81
 170         27,     // 'R', =82
 171         28,     // 'S', =83
 172         29,     // 'T', =84
 173         30,     // 'U', =85
 174         31,     // 'V', =86
 175         32,     // 'W', =87
 176         33,     // 'X', =88
 177         34,     // 'Y', =89
 178         35,     // 'Z', =90
 179     };
 180     if (c < ' ' || c > 'Z')
 181     {
 182         return CHIP_ERROR_INVALID_INTEGER_VALUE;
 183     }
 184     uint8_t v = decodes[c - ' '];
 185     if (v == kBogus)
 186     {
 187         return CHIP_ERROR_INVALID_INTEGER_VALUE;
 188     }
 189     value = v;
 190     return 0;
 191 }
 192
 193 CHIP_ERROR base41Decode(std::string base41, std::vector<uint8_t> & result)
 194 {
 195     result.clear();
 196
 197     for (size_t i = 0; base41.length() - i >= kBase41ChunkLen; i += kBase41ChunkLen)
 198     {
 199         uint16_t value = 0;
 200
 201         for (size_t iv = i + kBase41ChunkLen; iv > i; iv--)
 202         {
 203             uint8_t v;
 204             CHIP_ERROR err = decodeChar(base41[iv - 1], v);
 205
 206             if (err != CHIP_NO_ERROR)
 207             {
 208                 return err;
 209             }
 210
 211             value = static_cast<uint16_t>(value * kRadix + v);
 212         }
 213
 214         result.push_back(static_cast<uint8_t>(value % 256));
 215         // Cast is safe, because we divided a uint16_t by 256 to get here,
 216         // so what's left has to fit inside uint8_t.
 217         result.push_back(static_cast<uint8_t>(value / 256));
 218     }
 219
 220     if (base41.length() % kBase41ChunkLen != 0) // only 1 or 2 chars left
 221     {
 222         size_t tail    = (base41.length() % kBase41ChunkLen);
 223         size_t i       = base41.length() - tail;
 224         uint16_t value = 0;
 225
 226         for (size_t iv = base41.length(); iv > i; iv--)
 227         {
 228             uint8_t v;
 229             CHIP_ERROR err = decodeChar(base41[iv - 1], v);
 230
 231             if (err != CHIP_NO_ERROR)
 232             {
 233                 return err;
 234             }
 235
 236             value = static_cast<uint16_t>(value * kRadix + v);
 237         }
 238         result.push_back(static_cast<uint8_t>(value % 256));
 239         value /= 256;
 240         if (value != 0)
 241         {
 242             // Cast is safe, because we divided a uint16_t by 256 to get here,
 243             // so what's left has to fit inside uint8_t.
 244             result.push_back(static_cast<uint8_t>(value));
 245         }
 246     }
 247     return CHIP_NO_ERROR;
 248 }
 249
 250 } // namespace chip