diff options
Diffstat (limited to '')
43 files changed, 5685 insertions, 0 deletions
diff --git a/contrib/base32hex.c b/contrib/base32hex.c new file mode 100644 index 0000000..31c5bbd --- /dev/null +++ b/contrib/base32hex.c @@ -0,0 +1,277 @@ +/* Copyright (C) 2011-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ + +#include "base32hex.h" + +#include <stdlib.h> +#include <stdint.h> + +/*! \brief Maximal length of binary input to Base32hex encoding. */ +#define MAX_BIN_DATA_LEN ((INT32_MAX / 8) * 5) + +/*! \brief Base32hex padding character. */ +static const uint8_t base32hex_pad = '='; +/*! \brief Base32hex alphabet. Beware: original code was upper-case. */ +static const uint8_t base32hex_enc[] = "0123456789abcdefghijklmnopqrstuv"; + +/*! \brief Indicates bad Base32hex character. */ +#define KO 255 +/*! \brief Indicates Base32hex padding character. */ +#define PD 32 + +/*! \brief Transformation and validation table for decoding Base32hex. */ +static const uint8_t base32hex_dec[256] = { + [ 0] = KO, [ 43] = KO, ['V'] = 31, [129] = KO, [172] = KO, [215] = KO, + [ 1] = KO, [ 44] = KO, ['W'] = KO, [130] = KO, [173] = KO, [216] = KO, + [ 2] = KO, [ 45] = KO, ['X'] = KO, [131] = KO, [174] = KO, [217] = KO, + [ 3] = KO, [ 46] = KO, ['Y'] = KO, [132] = KO, [175] = KO, [218] = KO, + [ 4] = KO, [ 47] = KO, ['Z'] = KO, [133] = KO, [176] = KO, [219] = KO, + [ 5] = KO, ['0'] = 0, [ 91] = KO, [134] = KO, [177] = KO, [220] = KO, + [ 6] = KO, ['1'] = 1, [ 92] = KO, [135] = KO, [178] = KO, [221] = KO, + [ 7] = KO, ['2'] = 2, [ 93] = KO, [136] = KO, [179] = KO, [222] = KO, + [ 8] = KO, ['3'] = 3, [ 94] = KO, [137] = KO, [180] = KO, [223] = KO, + [ 9] = KO, ['4'] = 4, [ 95] = KO, [138] = KO, [181] = KO, [224] = KO, + [ 10] = KO, ['5'] = 5, [ 96] = KO, [139] = KO, [182] = KO, [225] = KO, + [ 11] = KO, ['6'] = 6, ['a'] = 10, [140] = KO, [183] = KO, [226] = KO, + [ 12] = KO, ['7'] = 7, ['b'] = 11, [141] = KO, [184] = KO, [227] = KO, + [ 13] = KO, ['8'] = 8, ['c'] = 12, [142] = KO, [185] = KO, [228] = KO, + [ 14] = KO, ['9'] = 9, ['d'] = 13, [143] = KO, [186] = KO, [229] = KO, + [ 15] = KO, [ 58] = KO, ['e'] = 14, [144] = KO, [187] = KO, [230] = KO, + [ 16] = KO, [ 59] = KO, ['f'] = 15, [145] = KO, [188] = KO, [231] = KO, + [ 17] = KO, [ 60] = KO, ['g'] = 16, [146] = KO, [189] = KO, [232] = KO, + [ 18] = KO, ['='] = PD, ['h'] = 17, [147] = KO, [190] = KO, [233] = KO, + [ 19] = KO, [ 62] = KO, ['i'] = 18, [148] = KO, [191] = KO, [234] = KO, + [ 20] = KO, [ 63] = KO, ['j'] = 19, [149] = KO, [192] = KO, [235] = KO, + [ 21] = KO, [ 64] = KO, ['k'] = 20, [150] = KO, [193] = KO, [236] = KO, + [ 22] = KO, ['A'] = 10, ['l'] = 21, [151] = KO, [194] = KO, [237] = KO, + [ 23] = KO, ['B'] = 11, ['m'] = 22, [152] = KO, [195] = KO, [238] = KO, + [ 24] = KO, ['C'] = 12, ['n'] = 23, [153] = KO, [196] = KO, [239] = KO, + [ 25] = KO, ['D'] = 13, ['o'] = 24, [154] = KO, [197] = KO, [240] = KO, + [ 26] = KO, ['E'] = 14, ['p'] = 25, [155] = KO, [198] = KO, [241] = KO, + [ 27] = KO, ['F'] = 15, ['q'] = 26, [156] = KO, [199] = KO, [242] = KO, + [ 28] = KO, ['G'] = 16, ['r'] = 27, [157] = KO, [200] = KO, [243] = KO, + [ 29] = KO, ['H'] = 17, ['s'] = 28, [158] = KO, [201] = KO, [244] = KO, + [ 30] = KO, ['I'] = 18, ['t'] = 29, [159] = KO, [202] = KO, [245] = KO, + [ 31] = KO, ['J'] = 19, ['u'] = 30, [160] = KO, [203] = KO, [246] = KO, + [ 32] = KO, ['K'] = 20, ['v'] = 31, [161] = KO, [204] = KO, [247] = KO, + [ 33] = KO, ['L'] = 21, ['w'] = KO, [162] = KO, [205] = KO, [248] = KO, + [ 34] = KO, ['M'] = 22, ['x'] = KO, [163] = KO, [206] = KO, [249] = KO, + [ 35] = KO, ['N'] = 23, ['y'] = KO, [164] = KO, [207] = KO, [250] = KO, + [ 36] = KO, ['O'] = 24, ['z'] = KO, [165] = KO, [208] = KO, [251] = KO, + [ 37] = KO, ['P'] = 25, [123] = KO, [166] = KO, [209] = KO, [252] = KO, + [ 38] = KO, ['Q'] = 26, [124] = KO, [167] = KO, [210] = KO, [253] = KO, + [ 39] = KO, ['R'] = 27, [125] = KO, [168] = KO, [211] = KO, [254] = KO, + [ 40] = KO, ['S'] = 28, [126] = KO, [169] = KO, [212] = KO, [255] = KO, + [ 41] = KO, ['T'] = 29, [127] = KO, [170] = KO, [213] = KO, + [ 42] = KO, ['U'] = 30, [128] = KO, [171] = KO, [214] = KO, +}; + +int32_t base32hex_decode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return -1; + } + if (in_len > INT32_MAX || out_len < ((in_len + 7) / 8) * 5) { + return -1; + } + if ((in_len % 8) != 0) { + return -1; + } + + const uint8_t *stop = in + in_len; + uint8_t *bin = out; + uint8_t pad_len = 0; + uint8_t c1, c2, c3, c4, c5, c6, c7, c8; + + // Decoding loop takes 8 characters and creates 5 bytes. + while (in < stop) { + // Filling and transforming 8 Base32hex chars. + c1 = base32hex_dec[in[0]]; + c2 = base32hex_dec[in[1]]; + c3 = base32hex_dec[in[2]]; + c4 = base32hex_dec[in[3]]; + c5 = base32hex_dec[in[4]]; + c6 = base32hex_dec[in[5]]; + c7 = base32hex_dec[in[6]]; + c8 = base32hex_dec[in[7]]; + + // Check 8. char if is bad or padding. + if (c8 >= PD) { + if (c8 == PD && pad_len == 0) { + pad_len = 1; + } else { + return -1; + } + } + + // Check 7. char if is bad or padding (if so, 6. must be too). + if (c7 >= PD) { + if (c7 == PD && c6 == PD && pad_len == 1) { + pad_len = 3; + } else { + return -1; + } + } + + // Check 6. char if is bad or padding. + if (c6 >= PD) { + if (!(c6 == PD && pad_len == 3)) { + return -1; + } + } + + // Check 5. char if is bad or padding. + if (c5 >= PD) { + if (c5 == PD && pad_len == 3) { + pad_len = 4; + } else { + return -1; + } + } + + // Check 4. char if is bad or padding (if so, 3. must be too). + if (c4 >= PD) { + if (c4 == PD && c3 == PD && pad_len == 4) { + pad_len = 6; + } else { + return -1; + } + } + + // Check 3. char if is bad or padding. + if (c3 >= PD) { + if (!(c3 == PD && pad_len == 6)) { + return -1; + } + } + + // 1. and 2. chars must not be padding. + if (c2 >= PD || c1 >= PD) { + return -1; + } + + // Computing of output data based on padding length. + switch (pad_len) { + case 0: + bin[4] = (c7 << 5) + c8; + case 1: + bin[3] = (c5 << 7) + (c6 << 2) + (c7 >> 3); + case 3: + bin[2] = (c4 << 4) + (c5 >> 1); + case 4: + bin[1] = (c2 << 6) + (c3 << 1) + (c4 >> 4); + case 6: + bin[0] = (c1 << 3) + (c2 >> 2); + } + + // Update output end. + switch (pad_len) { + case 0: + bin += 5; + break; + case 1: + bin += 4; + break; + case 3: + bin += 3; + break; + case 4: + bin += 2; + break; + case 6: + bin += 1; + break; + } + + in += 8; + } + + return (bin - out); +} + +int32_t base32hex_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return -1; + } + if (in_len > MAX_BIN_DATA_LEN || out_len < ((in_len + 4) / 5) * 8) { + return -1; + } + + uint8_t rest_len = in_len % 5; + const uint8_t *stop = in + in_len - rest_len; + uint8_t *text = out; + + // Encoding loop takes 5 bytes and creates 8 characters. + while (in < stop) { + text[0] = base32hex_enc[in[0] >> 3]; + text[1] = base32hex_enc[(in[0] & 0x07) << 2 | in[1] >> 6]; + text[2] = base32hex_enc[(in[1] & 0x3E) >> 1]; + text[3] = base32hex_enc[(in[1] & 0x01) << 4 | in[2] >> 4]; + text[4] = base32hex_enc[(in[2] & 0x0F) << 1 | in[3] >> 7]; + text[5] = base32hex_enc[(in[3] & 0x7C) >> 2]; + text[6] = base32hex_enc[(in[3] & 0x03) << 3 | in[4] >> 5]; + text[7] = base32hex_enc[in[4] & 0x1F]; + text += 8; + in += 5; + } + + // Processing of padding, if any. + switch (rest_len) { + case 4: + text[0] = base32hex_enc[in[0] >> 3]; + text[1] = base32hex_enc[(in[0] & 0x07) << 2 | in[1] >> 6]; + text[2] = base32hex_enc[(in[1] & 0x3E) >> 1]; + text[3] = base32hex_enc[(in[1] & 0x01) << 4 | in[2] >> 4]; + text[4] = base32hex_enc[(in[2] & 0x0F) << 1 | in[3] >> 7]; + text[5] = base32hex_enc[(in[3] & 0x7C) >> 2]; + text[6] = base32hex_enc[(in[3] & 0x03) << 3]; + text[7] = base32hex_pad; + text += 8; + break; + case 3: + text[0] = base32hex_enc[in[0] >> 3]; + text[1] = base32hex_enc[(in[0] & 0x07) << 2 | in[1] >> 6]; + text[2] = base32hex_enc[(in[1] & 0x3E) >> 1]; + text[3] = base32hex_enc[(in[1] & 0x01) << 4 | in[2] >> 4]; + text[4] = base32hex_enc[(in[2] & 0x0F) << 1]; + text[5] = base32hex_pad; + text[6] = base32hex_pad; + text[7] = base32hex_pad; + text += 8; + break; + case 2: + text[0] = base32hex_enc[in[0] >> 3]; + text[1] = base32hex_enc[(in[0] & 0x07) << 2 | in[1] >> 6]; + text[2] = base32hex_enc[(in[1] & 0x3E) >> 1]; + text[3] = base32hex_enc[(in[1] & 0x01) << 4]; + text[4] = base32hex_pad; + text[5] = base32hex_pad; + text[6] = base32hex_pad; + text[7] = base32hex_pad; + text += 8; + break; + case 1: + text[0] = base32hex_enc[in[0] >> 3]; + text[1] = base32hex_enc[(in[0] & 0x07) << 2]; + text[2] = base32hex_pad; + text[3] = base32hex_pad; + text[4] = base32hex_pad; + text[5] = base32hex_pad; + text[6] = base32hex_pad; + text[7] = base32hex_pad; + text += 8; + break; + } + + return (text - out); +} diff --git a/contrib/base32hex.h b/contrib/base32hex.h new file mode 100644 index 0000000..ed90cef --- /dev/null +++ b/contrib/base32hex.h @@ -0,0 +1,60 @@ +/* Copyright (C) 2011-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ +/*! + * \file + * + * \brief Base32hex implementation (RFC 4648). + * + * \note Input Base32hex string can contain a-v characters. These characters + * are considered as A-V equivalent. + * + * \addtogroup contrib + * @{ + */ + +#pragma once + +#include <stdint.h> + +/*! + * \brief Decodes text data using Base32hex. + * + * \note Input data needn't be terminated with '\0'. + * + * \note Input data must be continuous Base32hex string! + * + * \param in Input text data. + * \param in_len Length of input string. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output data. + * \retval KNOT_E* if error. + */ +int32_t base32hex_decode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + + +/*! + * \brief Encodes binary data using Base32hex. Lower case is used! + * + * \note Output data buffer contains Base32hex text string which isn't + * terminated with '\0'! + * + * \param in Input binary data. + * \param in_len Length of input data. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output string. + * \retval <0 if error. + */ +int32_t base32hex_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + +/*! @} */ diff --git a/contrib/base32hex.spdx b/contrib/base32hex.spdx new file mode 100644 index 0000000..7137645 --- /dev/null +++ b/contrib/base32hex.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: knotdns-base32hex +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-4f29f08d-5fbf-4793-934c-9a6a2e6d5517 + +PackageName: knotdns-base32hex +PackageDownloadLocation: git+https://gitlab.nic.cz/knot/knot-dns.git@2b3c828a4cb8d9595318552483d4947345426c30#src/libknot/internal/base32hex.c +PackageOriginator: Organization: Knot DNS contributors +PackageLicenseDeclared: GPL-3.0-or-later diff --git a/contrib/base64.c b/contrib/base64.c new file mode 100644 index 0000000..845b99c --- /dev/null +++ b/contrib/base64.c @@ -0,0 +1,260 @@ +/* Copyright (C) 2020 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ + +#include "base64.h" +#include "libknot/errcode.h" + +#include <stdlib.h> +#include <stdint.h> + +/*! \brief Maximal length of binary input to Base64 encoding. */ +#define MAX_BIN_DATA_LEN ((INT32_MAX / 4) * 3) + +/*! \brief Base64 padding character. */ +static const uint8_t base64_pad = '='; +/*! \brief Base64 alphabet. */ +static const uint8_t base64_enc[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; + +/*! \brief Indicates bad Base64 character. */ +#define KO 255 +/*! \brief Indicates Base64 padding character. */ +#define PD 64 + +/*! \brief Transformation and validation table for decoding Base64. */ +static const uint8_t base64_dec[256] = { + [ 0] = KO, ['+'] = 62, ['V'] = 21, [129] = KO, [172] = KO, [215] = KO, + [ 1] = KO, [ 44] = KO, ['W'] = 22, [130] = KO, [173] = KO, [216] = KO, + [ 2] = KO, [ 45] = KO, ['X'] = 23, [131] = KO, [174] = KO, [217] = KO, + [ 3] = KO, [ 46] = KO, ['Y'] = 24, [132] = KO, [175] = KO, [218] = KO, + [ 4] = KO, ['/'] = 63, ['Z'] = 25, [133] = KO, [176] = KO, [219] = KO, + [ 5] = KO, ['0'] = 52, [ 91] = KO, [134] = KO, [177] = KO, [220] = KO, + [ 6] = KO, ['1'] = 53, [ 92] = KO, [135] = KO, [178] = KO, [221] = KO, + [ 7] = KO, ['2'] = 54, [ 93] = KO, [136] = KO, [179] = KO, [222] = KO, + [ 8] = KO, ['3'] = 55, [ 94] = KO, [137] = KO, [180] = KO, [223] = KO, + [ 9] = KO, ['4'] = 56, [ 95] = KO, [138] = KO, [181] = KO, [224] = KO, + [ 10] = KO, ['5'] = 57, [ 96] = KO, [139] = KO, [182] = KO, [225] = KO, + [ 11] = KO, ['6'] = 58, ['a'] = 26, [140] = KO, [183] = KO, [226] = KO, + [ 12] = KO, ['7'] = 59, ['b'] = 27, [141] = KO, [184] = KO, [227] = KO, + [ 13] = KO, ['8'] = 60, ['c'] = 28, [142] = KO, [185] = KO, [228] = KO, + [ 14] = KO, ['9'] = 61, ['d'] = 29, [143] = KO, [186] = KO, [229] = KO, + [ 15] = KO, [ 58] = KO, ['e'] = 30, [144] = KO, [187] = KO, [230] = KO, + [ 16] = KO, [ 59] = KO, ['f'] = 31, [145] = KO, [188] = KO, [231] = KO, + [ 17] = KO, [ 60] = KO, ['g'] = 32, [146] = KO, [189] = KO, [232] = KO, + [ 18] = KO, ['='] = PD, ['h'] = 33, [147] = KO, [190] = KO, [233] = KO, + [ 19] = KO, [ 62] = KO, ['i'] = 34, [148] = KO, [191] = KO, [234] = KO, + [ 20] = KO, [ 63] = KO, ['j'] = 35, [149] = KO, [192] = KO, [235] = KO, + [ 21] = KO, [ 64] = KO, ['k'] = 36, [150] = KO, [193] = KO, [236] = KO, + [ 22] = KO, ['A'] = 0, ['l'] = 37, [151] = KO, [194] = KO, [237] = KO, + [ 23] = KO, ['B'] = 1, ['m'] = 38, [152] = KO, [195] = KO, [238] = KO, + [ 24] = KO, ['C'] = 2, ['n'] = 39, [153] = KO, [196] = KO, [239] = KO, + [ 25] = KO, ['D'] = 3, ['o'] = 40, [154] = KO, [197] = KO, [240] = KO, + [ 26] = KO, ['E'] = 4, ['p'] = 41, [155] = KO, [198] = KO, [241] = KO, + [ 27] = KO, ['F'] = 5, ['q'] = 42, [156] = KO, [199] = KO, [242] = KO, + [ 28] = KO, ['G'] = 6, ['r'] = 43, [157] = KO, [200] = KO, [243] = KO, + [ 29] = KO, ['H'] = 7, ['s'] = 44, [158] = KO, [201] = KO, [244] = KO, + [ 30] = KO, ['I'] = 8, ['t'] = 45, [159] = KO, [202] = KO, [245] = KO, + [ 31] = KO, ['J'] = 9, ['u'] = 46, [160] = KO, [203] = KO, [246] = KO, + [ 32] = KO, ['K'] = 10, ['v'] = 47, [161] = KO, [204] = KO, [247] = KO, + [ 33] = KO, ['L'] = 11, ['w'] = 48, [162] = KO, [205] = KO, [248] = KO, + [ 34] = KO, ['M'] = 12, ['x'] = 49, [163] = KO, [206] = KO, [249] = KO, + [ 35] = KO, ['N'] = 13, ['y'] = 50, [164] = KO, [207] = KO, [250] = KO, + [ 36] = KO, ['O'] = 14, ['z'] = 51, [165] = KO, [208] = KO, [251] = KO, + [ 37] = KO, ['P'] = 15, [123] = KO, [166] = KO, [209] = KO, [252] = KO, + [ 38] = KO, ['Q'] = 16, [124] = KO, [167] = KO, [210] = KO, [253] = KO, + [ 39] = KO, ['R'] = 17, [125] = KO, [168] = KO, [211] = KO, [254] = KO, + [ 40] = KO, ['S'] = 18, [126] = KO, [169] = KO, [212] = KO, [255] = KO, + [ 41] = KO, ['T'] = 19, [127] = KO, [170] = KO, [213] = KO, + [ 42] = KO, ['U'] = 20, [128] = KO, [171] = KO, [214] = KO, +}; + +int32_t kr_base64_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return KNOT_EINVAL; + } + if (in_len > MAX_BIN_DATA_LEN || out_len < ((in_len + 2) / 3) * 4) { + return KNOT_ERANGE; + } + + uint8_t rest_len = in_len % 3; + const uint8_t *stop = in + in_len - rest_len; + uint8_t *text = out; + + // Encoding loop takes 3 bytes and creates 4 characters. + while (in < stop) { + text[0] = base64_enc[in[0] >> 2]; + text[1] = base64_enc[(in[0] & 0x03) << 4 | in[1] >> 4]; + text[2] = base64_enc[(in[1] & 0x0F) << 2 | in[2] >> 6]; + text[3] = base64_enc[in[2] & 0x3F]; + text += 4; + in += 3; + } + + // Processing of padding, if any. + switch (rest_len) { + case 2: + text[0] = base64_enc[in[0] >> 2]; + text[1] = base64_enc[(in[0] & 0x03) << 4 | in[1] >> 4]; + text[2] = base64_enc[(in[1] & 0x0F) << 2]; + text[3] = base64_pad; + text += 4; + break; + case 1: + text[0] = base64_enc[in[0] >> 2]; + text[1] = base64_enc[(in[0] & 0x03) << 4]; + text[2] = base64_pad; + text[3] = base64_pad; + text += 4; + break; + } + + return (text - out); +} + +int32_t kr_base64_encode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out) +{ + // Checking inputs. + if (out == NULL) { + return KNOT_EINVAL; + } + if (in_len > MAX_BIN_DATA_LEN) { + return KNOT_ERANGE; + } + + // Compute output buffer length. + uint32_t out_len = ((in_len + 2) / 3) * 4; + + // Allocate output buffer. + *out = malloc(out_len); + if (*out == NULL) { + return KNOT_ENOMEM; + } + + // Encode data. + int32_t ret = kr_base64_encode(in, in_len, *out, out_len); + if (ret < 0) { + free(*out); + *out = NULL; + } + + return ret; +} + +int32_t kr_base64_decode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return KNOT_EINVAL; + } + if (in_len > INT32_MAX || out_len < ((in_len + 3) / 4) * 3) { + return KNOT_ERANGE; + } + if ((in_len % 4) != 0) { + return KNOT_BASE64_ESIZE; + } + + const uint8_t *stop = in + in_len; + uint8_t *bin = out; + uint8_t pad_len = 0; + uint8_t c1, c2, c3, c4; + + // Decoding loop takes 4 characters and creates 3 bytes. + while (in < stop) { + // Filling and transforming 4 Base64 chars. + c1 = base64_dec[in[0]]; + c2 = base64_dec[in[1]]; + c3 = base64_dec[in[2]]; + c4 = base64_dec[in[3]]; + + // Check 4. char if is bad or padding. + if (c4 >= PD) { + if (c4 == PD && pad_len == 0) { + pad_len = 1; + } else { + return KNOT_BASE64_ECHAR; + } + } + + // Check 3. char if is bad or padding. + if (c3 >= PD) { + if (c3 == PD && pad_len == 1) { + pad_len = 2; + } else { + return KNOT_BASE64_ECHAR; + } + } + + // Check 1. and 2. chars if are not padding. + if (c2 >= PD || c1 >= PD) { + return KNOT_BASE64_ECHAR; + } + + // Computing of output data based on padding length. + switch (pad_len) { + case 0: + bin[2] = (c3 << 6) + c4; + // FALLTHROUGH + case 1: + bin[1] = (c2 << 4) + (c3 >> 2); + // FALLTHROUGH + case 2: + bin[0] = (c1 << 2) + (c2 >> 4); + } + + // Update output end. + switch (pad_len) { + case 0: + bin += 3; + break; + case 1: + bin += 2; + break; + case 2: + bin += 1; + break; + } + + in += 4; + } + + return (bin - out); +} + +int32_t kr_base64_decode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out) +{ + // Checking inputs. + if (out == NULL) { + return KNOT_EINVAL; + } + + // Compute output buffer length. + uint32_t out_len = ((in_len + 3) / 4) * 3; + + // Allocate output buffer. + *out = malloc(out_len); + if (*out == NULL) { + return KNOT_ENOMEM; + } + + // Decode data. + int32_t ret = kr_base64_decode(in, in_len, *out, out_len); + if (ret < 0) { + free(*out); + *out = NULL; + } + + return ret; +} diff --git a/contrib/base64.h b/contrib/base64.h new file mode 100644 index 0000000..3c71431 --- /dev/null +++ b/contrib/base64.h @@ -0,0 +1,95 @@ +/* Copyright (C) 2011-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ +/*! + * \file + * + * \brief Base64 implementation (RFC 4648). + * + * \addtogroup contrib + * @{ + */ + +#pragma once + +#include <stdint.h> + +/*! + * \brief Encodes binary data using Base64. + * + * \note Output data buffer contains Base64 text string which isn't + * terminated with '\0'! + * + * \param in Input binary data. + * \param in_len Length of input data. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output string. + * \retval KNOT_E* if error. + */ +int32_t kr_base64_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + +/*! + * \brief Encodes binary data using Base64 and output stores to own buffer. + * + * \note Output data buffer contains Base64 text string which isn't + * terminated with '\0'! + * + * \note Output buffer should be deallocated after use. + * + * \param in Input binary data. + * \param in_len Length of input data. + * \param out Output data buffer. + * + * \retval >=0 length of output string. + * \retval KNOT_E* if error. + */ +int32_t kr_base64_encode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out); + +/*! + * \brief Decodes text data using Base64. + * + * \note Input data needn't be terminated with '\0'. + * + * \note Input data must be continuous Base64 string! + * + * \param in Input text data. + * \param in_len Length of input string. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output data. + * \retval KNOT_E* if error. + */ +int32_t kr_base64_decode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + +/*! + * \brief Decodes text data using Base64 and output stores to own buffer. + * + * \note Input data needn't be terminated with '\0'. + * + * \note Input data must be continuous Base64 string! + * + * \note Output buffer should be deallocated after use. + * + * \param in Input text data. + * \param in_len Length of input string. + * \param out Output data buffer. + * + * \retval >=0 length of output data. + * \retval KNOT_E* if error. + */ +int32_t kr_base64_decode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out); + +/*! @} */ diff --git a/contrib/base64.spdx b/contrib/base64.spdx new file mode 100644 index 0000000..15ce10d --- /dev/null +++ b/contrib/base64.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: knotdns-base64 +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-669dfa8c-3b50-425f-92fc-9b7ce18999f2 + +PackageName: knotdns-base64 +PackageDownloadLocation: git+https://gitlab.nic.cz/knot/knot-dns.git@2b3c828a4cb8d9595318552483d4947345426c30#src/libknot/internal/base64.c +PackageOriginator: Organization: Knot DNS contributors +PackageLicenseDeclared: GPL-3.0-or-later diff --git a/contrib/base64url.c b/contrib/base64url.c new file mode 100644 index 0000000..a015205 --- /dev/null +++ b/contrib/base64url.c @@ -0,0 +1,287 @@ +/* Copyright (C) 2020 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#include "contrib/base64url.h" +#include "libknot/errcode.h" + +#include <stdlib.h> +#include <stdint.h> +#include <ctype.h> + +/*! \brief Maximal length of binary input to Base64url encoding. */ +#define MAX_BIN_DATA_LEN ((INT32_MAX / 4) * 3) + +/*! \brief Base64url padding character. */ +static const uint8_t base64url_pad = '\0'; +/*! \brief Base64 alphabet. */ +static const uint8_t base64url_enc[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"; + +/*! \brief Indicates bad Base64 character. */ +#define KO 255 +/*! \brief Indicates Base64 padding character. */ +#define PD 64 + +/*! \brief Transformation and validation table for decoding Base64. */ +static const uint8_t base64url_dec[256] = { + [ 0] = PD, [ 43] = KO, ['V'] = 21, [129] = KO, [172] = KO, [215] = KO, + [ 1] = KO, [ 44] = KO, ['W'] = 22, [130] = KO, [173] = KO, [216] = KO, + [ 2] = KO, ['-'] = 62, ['X'] = 23, [131] = KO, [174] = KO, [217] = KO, + [ 3] = KO, [ 46] = KO, ['Y'] = 24, [132] = KO, [175] = KO, [218] = KO, + [ 4] = KO, [ 47] = KO, ['Z'] = 25, [133] = KO, [176] = KO, [219] = KO, + [ 5] = KO, ['0'] = 52, [ 91] = KO, [134] = KO, [177] = KO, [220] = KO, + [ 6] = KO, ['1'] = 53, [ 92] = KO, [135] = KO, [178] = KO, [221] = KO, + [ 7] = KO, ['2'] = 54, [ 93] = KO, [136] = KO, [179] = KO, [222] = KO, + [ 8] = KO, ['3'] = 55, [ 94] = KO, [137] = KO, [180] = KO, [223] = KO, + [ 9] = KO, ['4'] = 56, ['_'] = 63, [138] = KO, [181] = KO, [224] = KO, + [ 10] = KO, ['5'] = 57, [ 96] = KO, [139] = KO, [182] = KO, [225] = KO, + [ 11] = KO, ['6'] = 58, ['a'] = 26, [140] = KO, [183] = KO, [226] = KO, + [ 12] = KO, ['7'] = 59, ['b'] = 27, [141] = KO, [184] = KO, [227] = KO, + [ 13] = KO, ['8'] = 60, ['c'] = 28, [142] = KO, [185] = KO, [228] = KO, + [ 14] = KO, ['9'] = 61, ['d'] = 29, [143] = KO, [186] = KO, [229] = KO, + [ 15] = KO, [ 58] = KO, ['e'] = 30, [144] = KO, [187] = KO, [230] = KO, + [ 16] = KO, [ 59] = KO, ['f'] = 31, [145] = KO, [188] = KO, [231] = KO, + [ 17] = KO, [ 60] = KO, ['g'] = 32, [146] = KO, [189] = KO, [232] = KO, + [ 18] = KO, [ 61] = KO, ['h'] = 33, [147] = KO, [190] = KO, [233] = KO, + [ 19] = KO, [ 62] = KO, ['i'] = 34, [148] = KO, [191] = KO, [234] = KO, + [ 20] = KO, [ 63] = KO, ['j'] = 35, [149] = KO, [192] = KO, [235] = KO, + [ 21] = KO, [ 64] = KO, ['k'] = 36, [150] = KO, [193] = KO, [236] = KO, + [ 22] = KO, ['A'] = 0, ['l'] = 37, [151] = KO, [194] = KO, [237] = KO, + [ 23] = KO, ['B'] = 1, ['m'] = 38, [152] = KO, [195] = KO, [238] = KO, + [ 24] = KO, ['C'] = 2, ['n'] = 39, [153] = KO, [196] = KO, [239] = KO, + [ 25] = KO, ['D'] = 3, ['o'] = 40, [154] = KO, [197] = KO, [240] = KO, + [ 26] = KO, ['E'] = 4, ['p'] = 41, [155] = KO, [198] = KO, [241] = KO, + [ 27] = KO, ['F'] = 5, ['q'] = 42, [156] = KO, [199] = KO, [242] = KO, + [ 28] = KO, ['G'] = 6, ['r'] = 43, [157] = KO, [200] = KO, [243] = KO, + [ 29] = KO, ['H'] = 7, ['s'] = 44, [158] = KO, [201] = KO, [244] = KO, + [ 30] = KO, ['I'] = 8, ['t'] = 45, [159] = KO, [202] = KO, [245] = KO, + [ 31] = KO, ['J'] = 9, ['u'] = 46, [160] = KO, [203] = KO, [246] = KO, + [ 32] = KO, ['K'] = 10, ['v'] = 47, [161] = KO, [204] = KO, [247] = KO, + [ 33] = KO, ['L'] = 11, ['w'] = 48, [162] = KO, [205] = KO, [248] = KO, + [ 34] = KO, ['M'] = 12, ['x'] = 49, [163] = KO, [206] = KO, [249] = KO, + [ 35] = KO, ['N'] = 13, ['y'] = 50, [164] = KO, [207] = KO, [250] = KO, + [ 36] = KO, ['O'] = 14, ['z'] = 51, [165] = KO, [208] = KO, [251] = KO, + ['%'] = KO, ['P'] = 15, [123] = KO, [166] = KO, [209] = KO, [252] = KO, + [ 38] = KO, ['Q'] = 16, [124] = KO, [167] = KO, [210] = KO, [253] = KO, + [ 39] = KO, ['R'] = 17, [125] = KO, [168] = KO, [211] = KO, [254] = KO, + [ 40] = KO, ['S'] = 18, [126] = KO, [169] = KO, [212] = KO, [255] = KO, + [ 41] = KO, ['T'] = 19, [127] = KO, [170] = KO, [213] = KO, + [ 42] = KO, ['U'] = 20, [128] = KO, [171] = KO, [214] = KO, +}; + +int32_t kr_base64url_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return KNOT_EINVAL; + } + if (in_len > MAX_BIN_DATA_LEN || out_len < ((in_len + 2) / 3) * 4) { + return KNOT_ERANGE; + } + + uint8_t rest_len = in_len % 3; + const uint8_t *stop = in + in_len - rest_len; + uint8_t *text = out; + + // Encoding loop takes 3 bytes and creates 4 characters. + while (in < stop) { + text[0] = base64url_enc[in[0] >> 2]; + text[1] = base64url_enc[(in[0] & 0x03) << 4 | in[1] >> 4]; + text[2] = base64url_enc[(in[1] & 0x0F) << 2 | in[2] >> 6]; + text[3] = base64url_enc[in[2] & 0x3F]; + text += 4; + in += 3; + } + + // Processing of padding, if any. + switch (rest_len) { + case 2: + text[0] = base64url_enc[in[0] >> 2]; + text[1] = base64url_enc[(in[0] & 0x03) << 4 | in[1] >> 4]; + text[2] = base64url_enc[(in[1] & 0x0F) << 2]; + text[3] = base64url_pad; + text += 3; + break; + case 1: + text[0] = base64url_enc[in[0] >> 2]; + text[1] = base64url_enc[(in[0] & 0x03) << 4]; + text[2] = base64url_pad; + text[3] = base64url_pad; + text += 2; + break; + } + return (text - out); +} + +int32_t kr_base64url_encode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out) +{ + // Checking inputs. + if (out == NULL) { + return KNOT_EINVAL; + } + if (in_len > MAX_BIN_DATA_LEN) { + return KNOT_ERANGE; + } + + // Compute output buffer length. + uint32_t out_len = ((in_len + 2) / 3) * 4; + + // Allocate output buffer. + *out = malloc(out_len); + if (*out == NULL) { + return KNOT_ENOMEM; + } + + // Encode data. + int32_t ret = kr_base64url_encode(in, in_len, *out, out_len); + if (ret < 0) { + free(*out); + *out = NULL; + } + + return ret; +} + +int32_t kr_base64url_decode(const uint8_t *in, + uint32_t in_len, + uint8_t *out, + const uint32_t out_len) +{ + // Checking inputs. + if (in == NULL || out == NULL) { + return KNOT_EINVAL; + } + + // cut up to two "%3d" from the end of input + int pad3d = 0; + const uint8_t *end = in + in_len; + char *perc3d = "d3%d3%", *stop3d = perc3d + 6; + while (end != in && perc3d != stop3d && tolower(*--end) == *perc3d) { + if (*perc3d++ == '%') { + in_len -= 3; + pad3d++; + } + } + + if (in_len > INT32_MAX || out_len < ((in_len + 3) / 4) * 3) { + return KNOT_ERANGE; + } + + const uint8_t *stop = in + in_len; + uint8_t *bin = out; + uint8_t pad_len = 0; + uint8_t c1, c2, c3, c4; + + // Decoding loop takes 4 characters and creates 3 bytes. + while (in < stop) { + // Filling and transforming 4 Base64 chars. + c1 = base64url_dec[in[0]] ; + c2 = base64url_dec[in[1]] ; + c3 = (in + 2 < stop) ? base64url_dec[in[2]] : PD; + c4 = (in + 3 < stop) ? base64url_dec[in[3]] : PD; + + // Check 1. and 2. chars if are not padding + if (c1 >= PD || c2 >= PD) { + return KNOT_BASE64_ECHAR; + } + // Check 3. char if is bad or padding. + else if (c3 >= PD) { + if (c3 == PD) { + pad_len = 2; + } else { + return KNOT_BASE64_ECHAR; + } + } + // Check 3. char if is bad or padding. + else if (c4 >= PD) { + if (c4 == PD) { + pad_len = 1; + } else { + return KNOT_BASE64_ECHAR; + } + } + + if (pad_len > 0 && in <= stop - 4) { + return KNOT_BASE64_ECHAR; + } + + // Computing of output data based on padding length. + switch (pad_len) { + case 0: + bin[2] = (c3 << 6) + c4; + // FALLTHROUGH + case 1: + bin[1] = (c2 << 4) + (c3 >> 2); + // FALLTHROUGH + case 2: + bin[0] = (c1 << 2) + (c2 >> 4); + } + + // Update output end. + switch (pad_len) { + case 0: + bin += 3; + break; + case 1: + bin += 2; + goto end; + case 2: + bin += 1; + goto end; + } + + in += 4; + } + +end: + if (pad3d > pad_len) { + return KNOT_BASE64_ECHAR; + } + return (bin - out); +} + +int32_t kr_base64url_decode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out) +{ + // Checking inputs. + if (out == NULL) { + return KNOT_EINVAL; + } + + // Compute output buffer length. + uint32_t out_len = ((in_len + 3) / 4) * 3; + + // Allocate output buffer. + *out = malloc(out_len); + if (*out == NULL) { + return KNOT_ENOMEM; + } + + // Decode data. + int32_t ret = kr_base64url_decode(in, in_len, *out, out_len); + if (ret < 0) { + free(*out); + *out = NULL; + } + + return ret; +} diff --git a/contrib/base64url.h b/contrib/base64url.h new file mode 100644 index 0000000..875ecfa --- /dev/null +++ b/contrib/base64url.h @@ -0,0 +1,103 @@ +/* Copyright (C) 2020 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/*! + * \brief Base64url implementation (RFC 4648). + */ + +#pragma once + +#include <stdint.h> + +/*! + * \brief Encodes binary data using Base64. + * + * \note Output data buffer contains Base64 text string which isn't + * terminated with '\0'! + * + * \param in Input binary data. + * \param in_len Length of input data. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output string. + * \retval KNOT_E* if error. + */ +int32_t kr_base64url_encode(const uint8_t *in, + const uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + +/*! + * \brief Encodes binary data using Base64 and output stores to own buffer. + * + * \note Output data buffer contains Base64 text string which isn't + * terminated with '\0'! + * + * \note Output buffer should be deallocated after use. + * + * \param in Input binary data. + * \param in_len Length of input data. + * \param out Output data buffer. + * + * \retval >=0 length of output string. + * \retval KNOT_E* if error. + */ +int32_t kr_base64url_encode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out); + +/*! + * \brief Decodes text data using Base64. + * + * \note Input data needn't be terminated with '\0'. + * + * \note Input data must be continuous Base64 string! + * + * \param in Input text data. + * \param in_len Length of input string. + * \param out Output data buffer. + * \param out_len Size of output buffer. + * + * \retval >=0 length of output data. + * \retval KNOT_E* if error. + */ +int32_t kr_base64url_decode(const uint8_t *in, + uint32_t in_len, + uint8_t *out, + const uint32_t out_len); + +/*! + * \brief Decodes text data using Base64 and output stores to own buffer. + * + * \note Input data needn't be terminated with '\0'. + * + * \note Input data must be continuous Base64 string! + * + * \note Output buffer should be deallocated after use. + * + * \param in Input text data. + * \param in_len Length of input string. + * \param out Output data buffer. + * + * \retval >=0 length of output data. + * \retval KNOT_E* if error. + */ +int32_t kr_base64url_decode_alloc(const uint8_t *in, + const uint32_t in_len, + uint8_t **out); + +/*! @} */ diff --git a/contrib/ccan/asprintf/LICENSE b/contrib/ccan/asprintf/LICENSE new file mode 120000 index 0000000..2354d12 --- /dev/null +++ b/contrib/ccan/asprintf/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT
\ No newline at end of file diff --git a/contrib/ccan/asprintf/asprintf.c b/contrib/ccan/asprintf/asprintf.c new file mode 100644 index 0000000..4077599 --- /dev/null +++ b/contrib/ccan/asprintf/asprintf.c @@ -0,0 +1,57 @@ +/* SPDX-License-Identifier: MIT + * Source: https://ccodearchive.net/info/asprintf.html */ +#include <ccan/asprintf/asprintf.h> +#include <stdarg.h> +#include <stdio.h> + +char *PRINTF_FMT(1, 2) afmt(const char *fmt, ...) +{ + va_list ap; + char *ptr; + + va_start(ap, fmt); + /* The BSD version apparently sets ptr to NULL on fail. GNU loses. */ + if (vasprintf(&ptr, fmt, ap) < 0) + ptr = NULL; + va_end(ap); + return ptr; +} + +#if !HAVE_ASPRINTF +#include <stdarg.h> +#include <stdlib.h> + +int vasprintf(char **strp, const char *fmt, va_list ap) +{ + int len; + va_list ap_copy; + + /* We need to make a copy of ap, since it's a use-once. */ + va_copy(ap_copy, ap); + len = vsnprintf(NULL, 0, fmt, ap_copy); + va_end(ap_copy); + + /* Until version 2.0.6 glibc would return -1 on truncated output. + * OTOH, they had asprintf. */ + if (len < 0) + return -1; + + *strp = malloc(len+1); + if (!*strp) + return -1; + + return vsprintf(*strp, fmt, ap); +} + +int asprintf(char **strp, const char *fmt, ...) +{ + va_list ap; + int len; + + va_start(ap, fmt); + len = vasprintf(strp, fmt, ap); + va_end(ap); + + return len; +} +#endif /* !HAVE_ASPRINTF */ diff --git a/contrib/ccan/asprintf/asprintf.h b/contrib/ccan/asprintf/asprintf.h new file mode 100644 index 0000000..d4cc5ca --- /dev/null +++ b/contrib/ccan/asprintf/asprintf.h @@ -0,0 +1,51 @@ +/* SPDX-License-Identifier: MIT + * Source: https://ccodearchive.net/info/asprintf.html */ +#ifndef CCAN_ASPRINTF_H +#define CCAN_ASPRINTF_H +#include "config.h" +#include <ccan/compiler/compiler.h> + +/** + * afmt - allocate and populate a string with the given format. + * @fmt: printf-style format. + * + * This is a simplified asprintf interface. Returns NULL on error. + */ +char *PRINTF_FMT(1, 2) afmt(const char *fmt, ...); + +#if HAVE_ASPRINTF +#include <stdio.h> +#else +#include <stdarg.h> +/** + * asprintf - printf to a dynamically-allocated string. + * @strp: pointer to the string to allocate. + * @fmt: printf-style format. + * + * Returns -1 (and leaves @strp undefined) on an error. Otherwise returns + * number of bytes printed into @strp. + * + * Example: + * static char *greeting(const char *name) + * { + * char *str; + * int len = asprintf(&str, "Hello %s", name); + * if (len < 0) + * return NULL; + * return str; + * } + */ +int PRINTF_FMT(2, 3) asprintf(char **strp, const char *fmt, ...); + +/** + * vasprintf - vprintf to a dynamically-allocated string. + * @strp: pointer to the string to allocate. + * @fmt: printf-style format. + * + * Returns -1 (and leaves @strp undefined) on an error. Otherwise returns + * number of bytes printed into @strp. + */ +int vasprintf(char **strp, const char *fmt, va_list ap); +#endif + +#endif /* CCAN_ASPRINTF_H */ diff --git a/contrib/ccan/asprintf/asprintf.spdx b/contrib/ccan/asprintf/asprintf.spdx new file mode 100644 index 0000000..175078a --- /dev/null +++ b/contrib/ccan/asprintf/asprintf.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: ccan-asprintf +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-40d4b71d-00e9-4e75-b6da-559203e6b815 + +PackageName: asprintf +PackageDownloadLocation: git+https://github.com/rustyrussell/ccan@fb1dfd092940905883ea6473162f5f6e36624da2#ccan/asprintf +PackageOriginator: Person: Rusty Russell (rusty@rustcorp.com.au) +PackageLicenseDeclared: MIT diff --git a/contrib/ccan/compiler/LICENSE b/contrib/ccan/compiler/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/contrib/ccan/compiler/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/contrib/ccan/compiler/compiler.h b/contrib/ccan/compiler/compiler.h new file mode 100644 index 0000000..7c4f955 --- /dev/null +++ b/contrib/ccan/compiler/compiler.h @@ -0,0 +1,232 @@ +/* SPDX-License-Identifier: CC0-1.0 + * Source: https://ccodearchive.net/info/compiler.html */ +#ifndef CCAN_COMPILER_H +#define CCAN_COMPILER_H +#include "config.h" + +#ifndef COLD +#if HAVE_ATTRIBUTE_COLD +/** + * COLD - a function is unlikely to be called. + * + * Used to mark an unlikely code path and optimize appropriately. + * It is usually used on logging or error routines. + * + * Example: + * static void COLD moan(const char *reason) + * { + * fprintf(stderr, "Error: %s (%s)\n", reason, strerror(errno)); + * } + */ +#define COLD __attribute__((__cold__)) +#else +#define COLD +#endif +#endif + +#ifndef NORETURN +#if HAVE_ATTRIBUTE_NORETURN +/** + * NORETURN - a function does not return + * + * Used to mark a function which exits; useful for suppressing warnings. + * + * Example: + * static void NORETURN fail(const char *reason) + * { + * fprintf(stderr, "Error: %s (%s)\n", reason, strerror(errno)); + * exit(1); + * } + */ +#define NORETURN __attribute__((__noreturn__)) +#else +#define NORETURN +#endif +#endif + +#ifndef PRINTF_FMT +#if HAVE_ATTRIBUTE_PRINTF +/** + * PRINTF_FMT - a function takes printf-style arguments + * @nfmt: the 1-based number of the function's format argument. + * @narg: the 1-based number of the function's first variable argument. + * + * This allows the compiler to check your parameters as it does for printf(). + * + * Example: + * void PRINTF_FMT(2,3) my_printf(const char *prefix, const char *fmt, ...); + */ +#define PRINTF_FMT(nfmt, narg) \ + __attribute__((format(__printf__, nfmt, narg))) +#else +#define PRINTF_FMT(nfmt, narg) +#endif +#endif + +#ifndef CONST_FUNCTION +#if HAVE_ATTRIBUTE_CONST +/** + * CONST_FUNCTION - a function's return depends only on its argument + * + * This allows the compiler to assume that the function will return the exact + * same value for the exact same arguments. This implies that the function + * must not use global variables, or dereference pointer arguments. + */ +#define CONST_FUNCTION __attribute__((__const__)) +#else +#define CONST_FUNCTION +#endif + +#ifndef PURE_FUNCTION +#if HAVE_ATTRIBUTE_PURE +/** + * PURE_FUNCTION - a function is pure + * + * A pure function is one that has no side effects other than it's return value + * and uses no inputs other than it's arguments and global variables. + */ +#define PURE_FUNCTION __attribute__((__pure__)) +#else +#define PURE_FUNCTION +#endif +#endif +#endif + +#if HAVE_ATTRIBUTE_UNUSED +#ifndef UNNEEDED +/** + * UNNEEDED - a variable/function may not be needed + * + * This suppresses warnings about unused variables or functions, but tells + * the compiler that if it is unused it need not emit it into the source code. + * + * Example: + * // With some preprocessor options, this is unnecessary. + * static UNNEEDED int counter; + * + * // With some preprocessor options, this is unnecessary. + * static UNNEEDED void add_to_counter(int add) + * { + * counter += add; + * } + */ +#define UNNEEDED __attribute__((__unused__)) +#endif + +#ifndef NEEDED +#if HAVE_ATTRIBUTE_USED +/** + * NEEDED - a variable/function is needed + * + * This suppresses warnings about unused variables or functions, but tells + * the compiler that it must exist even if it (seems) unused. + * + * Example: + * // Even if this is unused, these are vital for debugging. + * static NEEDED int counter; + * static NEEDED void dump_counter(void) + * { + * printf("Counter is %i\n", counter); + * } + */ +#define NEEDED __attribute__((__used__)) +#else +/* Before used, unused functions and vars were always emitted. */ +#define NEEDED __attribute__((__unused__)) +#endif +#endif + +#ifndef UNUSED +/** + * UNUSED - a parameter is unused + * + * Some compilers (eg. gcc with -W or -Wunused) warn about unused + * function parameters. This suppresses such warnings and indicates + * to the reader that it's deliberate. + * + * Example: + * // This is used as a callback, so needs to have this prototype. + * static int some_callback(void *unused UNUSED) + * { + * return 0; + * } + */ +#define UNUSED __attribute__((__unused__)) +#endif +#else +#ifndef UNNEEDED +#define UNNEEDED +#endif +#ifndef NEEDED +#define NEEDED +#endif +#ifndef UNUSED +#define UNUSED +#endif +#endif + +#ifndef IS_COMPILE_CONSTANT +#if HAVE_BUILTIN_CONSTANT_P +/** + * IS_COMPILE_CONSTANT - does the compiler know the value of this expression? + * @expr: the expression to evaluate + * + * When an expression manipulation is complicated, it is usually better to + * implement it in a function. However, if the expression being manipulated is + * known at compile time, it is better to have the compiler see the entire + * expression so it can simply substitute the result. + * + * This can be done using the IS_COMPILE_CONSTANT() macro. + * + * Example: + * enum greek { ALPHA, BETA, GAMMA, DELTA, EPSILON }; + * + * // Out-of-line version. + * const char *greek_name(enum greek greek); + * + * // Inline version. + * static inline const char *_greek_name(enum greek greek) + * { + * switch (greek) { + * case ALPHA: return "alpha"; + * case BETA: return "beta"; + * case GAMMA: return "gamma"; + * case DELTA: return "delta"; + * case EPSILON: return "epsilon"; + * default: return "**INVALID**"; + * } + * } + * + * // Use inline if compiler knows answer. Otherwise call function + * // to avoid copies of the same code everywhere. + * #define greek_name(g) \ + * (IS_COMPILE_CONSTANT(greek) ? _greek_name(g) : greek_name(g)) + */ +#define IS_COMPILE_CONSTANT(expr) __builtin_constant_p(expr) +#else +/* If we don't know, assume it's not. */ +#define IS_COMPILE_CONSTANT(expr) 0 +#endif +#endif + +#ifndef WARN_UNUSED_RESULT +#if HAVE_WARN_UNUSED_RESULT +/** + * WARN_UNUSED_RESULT - warn if a function return value is unused. + * + * Used to mark a function where it is extremely unlikely that the caller + * can ignore the result, eg realloc(). + * + * Example: + * // buf param may be freed by this; need return value! + * static char *WARN_UNUSED_RESULT enlarge(char *buf, unsigned *size) + * { + * return realloc(buf, (*size) *= 2); + * } + */ +#define WARN_UNUSED_RESULT __attribute__((__warn_unused_result__)) +#else +#define WARN_UNUSED_RESULT +#endif +#endif +#endif /* CCAN_COMPILER_H */ diff --git a/contrib/ccan/compiler/compiler.spdx b/contrib/ccan/compiler/compiler.spdx new file mode 100644 index 0000000..45f19f4 --- /dev/null +++ b/contrib/ccan/compiler/compiler.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: ccan-compiler +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-1569e849-880d-4ce7-ba3e-f4aaec8fce52 + +PackageName: compiler +PackageDownloadLocation: git+https://github.com/rustyrussell/ccan@23e96f89d54b8d5c4675284bbcd44fba68d8f826#ccan/compiler +PackageOriginator: Person: Rusty Russell (rusty@rustcorp.com.au) +PackageLicenseDeclared: CC0-1.0 diff --git a/contrib/ccan/json/LICENSE b/contrib/ccan/json/LICENSE new file mode 120000 index 0000000..2354d12 --- /dev/null +++ b/contrib/ccan/json/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT
\ No newline at end of file diff --git a/contrib/ccan/json/json.c b/contrib/ccan/json/json.c new file mode 100644 index 0000000..a86c4db --- /dev/null +++ b/contrib/ccan/json/json.c @@ -0,0 +1,1362 @@ +/* SPDX-License-Identifier: MIT + * Source: https://ccodearchive.net/info/json.html + * Copyright (C) 2011 Joseph A. Adams (joeyadams3.14159@gmail.com) */ + +#include "json.h" + +#include <assert.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define out_of_memory() do { \ + fprintf(stderr, "Out of memory.\n"); \ + exit(EXIT_FAILURE); \ + } while (0) + +/* Sadly, strdup is not portable. */ +static char *json_strdup(const char *str) +{ + char *ret = (char*) malloc(strlen(str) + 1); + if (ret == NULL) + out_of_memory(); + strcpy(ret, str); + return ret; +} + +/* String buffer */ + +typedef struct +{ + char *cur; + char *end; + char *start; +} SB; + +static void sb_init(SB *sb) +{ + sb->start = (char*) malloc(17); + if (sb->start == NULL) + out_of_memory(); + sb->cur = sb->start; + sb->end = sb->start + 16; +} + +/* sb and need may be evaluated multiple times. */ +#define sb_need(sb, need) do { \ + if ((sb)->end - (sb)->cur < (need)) \ + sb_grow(sb, need); \ + } while (0) + +static void sb_grow(SB *sb, int need) +{ + size_t length = sb->cur - sb->start; + size_t alloc = sb->end - sb->start; + + do { + alloc *= 2; + } while (alloc < length + need); + + sb->start = (char*) realloc(sb->start, alloc + 1); + if (sb->start == NULL) + out_of_memory(); + sb->cur = sb->start + length; + sb->end = sb->start + alloc; +} + +static void sb_put(SB *sb, const char *bytes, int count) +{ + sb_need(sb, count); + memcpy(sb->cur, bytes, count); + sb->cur += count; +} + +#define sb_putc(sb, c) do { \ + if ((sb)->cur >= (sb)->end) \ + sb_grow(sb, 1); \ + *(sb)->cur++ = (c); \ + } while (0) + +static void sb_puts(SB *sb, const char *str) +{ + sb_put(sb, str, strlen(str)); +} + +static char *sb_finish(SB *sb) +{ + *sb->cur = 0; + assert(sb->start <= sb->cur && strlen(sb->start) == (size_t)(sb->cur - sb->start)); + return sb->start; +} + +static void sb_free(SB *sb) +{ + free(sb->start); +} + +/* + * Unicode helper functions + * + * These are taken from the ccan/charset module and customized a bit. + * Putting them here means the compiler can (choose to) inline them, + * and it keeps ccan/json from having a dependency. + */ + +/* + * Type for Unicode codepoints. + * We need our own because wchar_t might be 16 bits. + */ +typedef uint32_t uchar_t; + +/* + * Validate a single UTF-8 character starting at @s. + * The string must be null-terminated. + * + * If it's valid, return its length (1 thru 4). + * If it's invalid or clipped, return 0. + * + * This function implements the syntax given in RFC3629, which is + * the same as that given in The Unicode Standard, Version 6.0. + * + * It has the following properties: + * + * * All codepoints U+0000..U+10FFFF may be encoded, + * except for U+D800..U+DFFF, which are reserved + * for UTF-16 surrogate pair encoding. + * * UTF-8 byte sequences longer than 4 bytes are not permitted, + * as they exceed the range of Unicode. + * * The sixty-six Unicode "non-characters" are permitted + * (namely, U+FDD0..U+FDEF, U+xxFFFE, and U+xxFFFF). + */ +static int utf8_validate_cz(const char *s) +{ + unsigned char c = *s++; + + if (c <= 0x7F) { /* 00..7F */ + return 1; + } else if (c <= 0xC1) { /* 80..C1 */ + /* Disallow overlong 2-byte sequence. */ + return 0; + } else if (c <= 0xDF) { /* C2..DF */ + /* Make sure subsequent byte is in the range 0x80..0xBF. */ + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + + return 2; + } else if (c <= 0xEF) { /* E0..EF */ + /* Disallow overlong 3-byte sequence. */ + if (c == 0xE0 && (unsigned char)*s < 0xA0) + return 0; + + /* Disallow U+D800..U+DFFF. */ + if (c == 0xED && (unsigned char)*s > 0x9F) + return 0; + + /* Make sure subsequent bytes are in the range 0x80..0xBF. */ + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + + return 3; + } else if (c <= 0xF4) { /* F0..F4 */ + /* Disallow overlong 4-byte sequence. */ + if (c == 0xF0 && (unsigned char)*s < 0x90) + return 0; + + /* Disallow codepoints beyond U+10FFFF. */ + if (c == 0xF4 && (unsigned char)*s > 0x8F) + return 0; + + /* Make sure subsequent bytes are in the range 0x80..0xBF. */ + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + if (((unsigned char)*s++ & 0xC0) != 0x80) + return 0; + + return 4; + } else { /* F5..FF */ + return 0; + } +} + +/* Validate a null-terminated UTF-8 string. */ +static bool utf8_validate(const char *s) +{ + int len; + + for (; *s != 0; s += len) { + len = utf8_validate_cz(s); + if (len == 0) + return false; + } + + return true; +} + +/* + * Read a single UTF-8 character starting at @s, + * returning the length, in bytes, of the character read. + * + * This function assumes input is valid UTF-8, + * and that there are enough characters in front of @s. + */ +static int utf8_read_char(const char *s, uchar_t *out) +{ + const unsigned char *c = (const unsigned char*) s; + + assert(utf8_validate_cz(s)); + + if (c[0] <= 0x7F) { + /* 00..7F */ + *out = c[0]; + return 1; + } else if (c[0] <= 0xDF) { + /* C2..DF (unless input is invalid) */ + *out = ((uchar_t)c[0] & 0x1F) << 6 | + ((uchar_t)c[1] & 0x3F); + return 2; + } else if (c[0] <= 0xEF) { + /* E0..EF */ + *out = ((uchar_t)c[0] & 0xF) << 12 | + ((uchar_t)c[1] & 0x3F) << 6 | + ((uchar_t)c[2] & 0x3F); + return 3; + } else { + /* F0..F4 (unless input is invalid) */ + *out = ((uchar_t)c[0] & 0x7) << 18 | + ((uchar_t)c[1] & 0x3F) << 12 | + ((uchar_t)c[2] & 0x3F) << 6 | + ((uchar_t)c[3] & 0x3F); + return 4; + } +} + +/* + * Write a single UTF-8 character to @s, + * returning the length, in bytes, of the character written. + * + * @unicode must be U+0000..U+10FFFF, but not U+D800..U+DFFF. + * + * This function will write up to 4 bytes to @out. + */ +static int utf8_write_char(uchar_t unicode, char *out) +{ + unsigned char *o = (unsigned char*) out; + + assert(unicode <= 0x10FFFF && !(unicode >= 0xD800 && unicode <= 0xDFFF)); + + if (unicode <= 0x7F) { + /* U+0000..U+007F */ + *o++ = unicode; + return 1; + } else if (unicode <= 0x7FF) { + /* U+0080..U+07FF */ + *o++ = 0xC0 | unicode >> 6; + *o++ = 0x80 | (unicode & 0x3F); + return 2; + } else if (unicode <= 0xFFFF) { + /* U+0800..U+FFFF */ + *o++ = 0xE0 | unicode >> 12; + *o++ = 0x80 | (unicode >> 6 & 0x3F); + *o++ = 0x80 | (unicode & 0x3F); + return 3; + } else { + /* U+10000..U+10FFFF */ + *o++ = 0xF0 | unicode >> 18; + *o++ = 0x80 | (unicode >> 12 & 0x3F); + *o++ = 0x80 | (unicode >> 6 & 0x3F); + *o++ = 0x80 | (unicode & 0x3F); + return 4; + } +} + +/* + * Compute the Unicode codepoint of a UTF-16 surrogate pair. + * + * @uc should be 0xD800..0xDBFF, and @lc should be 0xDC00..0xDFFF. + * If they aren't, this function returns false. + */ +static bool from_surrogate_pair(uint16_t uc, uint16_t lc, uchar_t *unicode) +{ + if (uc >= 0xD800 && uc <= 0xDBFF && lc >= 0xDC00 && lc <= 0xDFFF) { + *unicode = 0x10000 + ((((uchar_t)uc & 0x3FF) << 10) | (lc & 0x3FF)); + return true; + } else { + return false; + } +} + +/* + * Construct a UTF-16 surrogate pair given a Unicode codepoint. + * + * @unicode must be U+10000..U+10FFFF. + */ +static void to_surrogate_pair(uchar_t unicode, uint16_t *uc, uint16_t *lc) +{ + uchar_t n; + + assert(unicode >= 0x10000 && unicode <= 0x10FFFF); + + n = unicode - 0x10000; + *uc = ((n >> 10) & 0x3FF) | 0xD800; + *lc = (n & 0x3FF) | 0xDC00; +} + +#define is_space(c) ((c) == '\t' || (c) == '\n' || (c) == '\r' || (c) == ' ') +#define is_digit(c) ((c) >= '0' && (c) <= '9') + +static bool parse_value (const char **sp, JsonNode **out); +static bool parse_string (const char **sp, char **out); +static bool parse_number (const char **sp, double *out); +static bool parse_array (const char **sp, JsonNode **out); +static bool parse_object (const char **sp, JsonNode **out); +static bool parse_hex16 (const char **sp, uint16_t *out); + +static bool expect_literal (const char **sp, const char *str); +static void skip_space (const char **sp); + +static void emit_value (SB *out, const JsonNode *node); +static void emit_value_indented (SB *out, const JsonNode *node, const char *space, int indent_level); +static void emit_string (SB *out, const char *str); +static void emit_number (SB *out, double num); +static void emit_array (SB *out, const JsonNode *array); +static void emit_array_indented (SB *out, const JsonNode *array, const char *space, int indent_level); +static void emit_object (SB *out, const JsonNode *object); +static void emit_object_indented (SB *out, const JsonNode *object, const char *space, int indent_level); + +static int write_hex16(char *out, uint16_t val); + +static JsonNode *mknode(JsonTag tag); +static void append_node(JsonNode *parent, JsonNode *child); +static void prepend_node(JsonNode *parent, JsonNode *child); +static void append_member(JsonNode *object, char *key, JsonNode *value); + +/* Assertion-friendly validity checks */ +static bool tag_is_valid(unsigned int tag); +static bool number_is_valid(const char *num); + +JsonNode *json_decode(const char *json) +{ + const char *s = json; + JsonNode *ret; + + skip_space(&s); + if (!parse_value(&s, &ret)) + return NULL; + + skip_space(&s); + if (*s != 0) { + json_delete(ret); + return NULL; + } + + return ret; +} + +char *json_encode(const JsonNode *node) +{ + return json_stringify(node, NULL); +} + +char *json_encode_string(const char *str) +{ + SB sb; + sb_init(&sb); + + emit_string(&sb, str); + + return sb_finish(&sb); +} + +char *json_stringify(const JsonNode *node, const char *space) +{ + SB sb; + sb_init(&sb); + + if (space != NULL) + emit_value_indented(&sb, node, space, 0); + else + emit_value(&sb, node); + + return sb_finish(&sb); +} + +void json_delete(JsonNode *node) +{ + if (node != NULL) { + json_remove_from_parent(node); + + switch (node->tag) { + case JSON_STRING: + free(node->string_); + break; + case JSON_ARRAY: + case JSON_OBJECT: + { + JsonNode *child, *next; + for (child = node->children.head; child != NULL; child = next) { + next = child->next; + json_delete(child); + } + break; + } + default:; + } + + free(node); + } +} + +bool json_validate(const char *json) +{ + const char *s = json; + + skip_space(&s); + if (!parse_value(&s, NULL)) + return false; + + skip_space(&s); + if (*s != 0) + return false; + + return true; +} + +JsonNode *json_find_element(JsonNode *array, int index) +{ + JsonNode *element; + int i = 0; + + if (array == NULL || array->tag != JSON_ARRAY) + return NULL; + + json_foreach(element, array) { + if (i == index) + return element; + i++; + } + + return NULL; +} + +JsonNode *json_find_member(JsonNode *object, const char *name) +{ + JsonNode *member; + + if (object == NULL || object->tag != JSON_OBJECT) + return NULL; + + json_foreach(member, object) + if (strcmp(member->key, name) == 0) + return member; + + return NULL; +} + +JsonNode *json_first_child(const JsonNode *node) +{ + if (node != NULL && (node->tag == JSON_ARRAY || node->tag == JSON_OBJECT)) + return node->children.head; + return NULL; +} + +static JsonNode *mknode(JsonTag tag) +{ + JsonNode *ret = (JsonNode*) calloc(1, sizeof(JsonNode)); + if (ret == NULL) + out_of_memory(); + ret->tag = tag; + return ret; +} + +JsonNode *json_mknull(void) +{ + return mknode(JSON_NULL); +} + +JsonNode *json_mkbool(bool b) +{ + JsonNode *ret = mknode(JSON_BOOL); + ret->bool_ = b; + return ret; +} + +static JsonNode *mkstring(char *s) +{ + JsonNode *ret = mknode(JSON_STRING); + ret->string_ = s; + return ret; +} + +JsonNode *json_mkstring(const char *s) +{ + return mkstring(json_strdup(s)); +} + +JsonNode *json_mknumber(double n) +{ + JsonNode *node = mknode(JSON_NUMBER); + node->number_ = n; + return node; +} + +JsonNode *json_mkarray(void) +{ + return mknode(JSON_ARRAY); +} + +JsonNode *json_mkobject(void) +{ + return mknode(JSON_OBJECT); +} + +static void append_node(JsonNode *parent, JsonNode *child) +{ + child->parent = parent; + child->prev = parent->children.tail; + child->next = NULL; + + if (parent->children.tail != NULL) + parent->children.tail->next = child; + else + parent->children.head = child; + parent->children.tail = child; +} + +static void prepend_node(JsonNode *parent, JsonNode *child) +{ + child->parent = parent; + child->prev = NULL; + child->next = parent->children.head; + + if (parent->children.head != NULL) + parent->children.head->prev = child; + else + parent->children.tail = child; + parent->children.head = child; +} + +static void append_member(JsonNode *object, char *key, JsonNode *value) +{ + value->key = key; + append_node(object, value); +} + +void json_append_element(JsonNode *array, JsonNode *element) +{ + assert(array->tag == JSON_ARRAY); + assert(element->parent == NULL); + + append_node(array, element); +} + +void json_prepend_element(JsonNode *array, JsonNode *element) +{ + assert(array->tag == JSON_ARRAY); + assert(element->parent == NULL); + + prepend_node(array, element); +} + +void json_append_member(JsonNode *object, const char *key, JsonNode *value) +{ + assert(object->tag == JSON_OBJECT); + assert(value->parent == NULL); + + append_member(object, json_strdup(key), value); +} + +void json_prepend_member(JsonNode *object, const char *key, JsonNode *value) +{ + assert(object->tag == JSON_OBJECT); + assert(value->parent == NULL); + + value->key = json_strdup(key); + prepend_node(object, value); +} + +void json_remove_from_parent(JsonNode *node) +{ + JsonNode *parent = node->parent; + + if (parent != NULL) { + if (node->prev != NULL) + node->prev->next = node->next; + else + parent->children.head = node->next; + if (node->next != NULL) + node->next->prev = node->prev; + else + parent->children.tail = node->prev; + + free(node->key); + + node->parent = NULL; + node->prev = node->next = NULL; + node->key = NULL; + } +} + +static bool parse_value(const char **sp, JsonNode **out) +{ + const char *s = *sp; + + switch (*s) { + case 'n': + if (expect_literal(&s, "null")) { + if (out) + *out = json_mknull(); + *sp = s; + return true; + } + return false; + + case 'f': + if (expect_literal(&s, "false")) { + if (out) + *out = json_mkbool(false); + *sp = s; + return true; + } + return false; + + case 't': + if (expect_literal(&s, "true")) { + if (out) + *out = json_mkbool(true); + *sp = s; + return true; + } + return false; + + case '"': { + char *str; + if (parse_string(&s, out ? &str : NULL)) { + if (out) + *out = mkstring(str); + *sp = s; + return true; + } + return false; + } + + case '[': + if (parse_array(&s, out)) { + *sp = s; + return true; + } + return false; + + case '{': + if (parse_object(&s, out)) { + *sp = s; + return true; + } + return false; + + default: { + double num; + if (parse_number(&s, out ? &num : NULL)) { + if (out) + *out = json_mknumber(num); + *sp = s; + return true; + } + return false; + } + } +} + +static bool parse_array(const char **sp, JsonNode **out) +{ + const char *s = *sp; + JsonNode *ret = out ? json_mkarray() : NULL; + JsonNode *element; + + if (*s++ != '[') + goto failure; + skip_space(&s); + + if (*s == ']') { + s++; + goto success; + } + + for (;;) { + if (!parse_value(&s, out ? &element : NULL)) + goto failure; + skip_space(&s); + + if (out) + json_append_element(ret, element); + + if (*s == ']') { + s++; + goto success; + } + + if (*s++ != ',') + goto failure; + skip_space(&s); + } + +success: + *sp = s; + if (out) + *out = ret; + return true; + +failure: + json_delete(ret); + return false; +} + +static bool parse_object(const char **sp, JsonNode **out) +{ + const char *s = *sp; + JsonNode *ret = out ? json_mkobject() : NULL; + char *key; + JsonNode *value; + + if (*s++ != '{') + goto failure; + skip_space(&s); + + if (*s == '}') { + s++; + goto success; + } + + for (;;) { + if (!parse_string(&s, out ? &key : NULL)) + goto failure; + skip_space(&s); + + if (*s++ != ':') + goto failure_free_key; + skip_space(&s); + + if (!parse_value(&s, out ? &value : NULL)) + goto failure_free_key; + skip_space(&s); + + if (out) + append_member(ret, key, value); + + if (*s == '}') { + s++; + goto success; + } + + if (*s++ != ',') + goto failure; + skip_space(&s); + } + +success: + *sp = s; + if (out) + *out = ret; + return true; + +failure_free_key: + if (out) + free(key); +failure: + json_delete(ret); + return false; +} + +bool parse_string(const char **sp, char **out) +{ + const char *s = *sp; + SB sb = { NULL, NULL, NULL }; + char throwaway_buffer[4]; + /* enough space for a UTF-8 character */ + char *b; + + if (*s++ != '"') + return false; + + if (out) { + sb_init(&sb); + sb_need(&sb, 4); + b = sb.cur; + } else { + b = throwaway_buffer; + } + + while (*s != '"') { + unsigned char c = *s++; + + /* Parse next character, and write it to b. */ + if (c == '\\') { + c = *s++; + switch (c) { + case '"': + case '\\': + case '/': + *b++ = c; + break; + case 'b': + *b++ = '\b'; + break; + case 'f': + *b++ = '\f'; + break; + case 'n': + *b++ = '\n'; + break; + case 'r': + *b++ = '\r'; + break; + case 't': + *b++ = '\t'; + break; + case 'u': + { + uint16_t uc, lc; + uchar_t unicode; + + if (!parse_hex16(&s, &uc)) + goto failed; + + if (uc >= 0xD800 && uc <= 0xDFFF) { + /* Handle UTF-16 surrogate pair. */ + if (*s++ != '\\' || *s++ != 'u' || !parse_hex16(&s, &lc)) + goto failed; /* Incomplete surrogate pair. */ + if (!from_surrogate_pair(uc, lc, &unicode)) + goto failed; /* Invalid surrogate pair. */ + } else if (uc == 0) { + /* Disallow "\u0000". */ + goto failed; + } else { + unicode = uc; + } + + b += utf8_write_char(unicode, b); + break; + } + default: + /* Invalid escape */ + goto failed; + } + } else if (c <= 0x1F) { + /* Control characters are not allowed in string literals. */ + goto failed; + } else { + /* Validate and echo a UTF-8 character. */ + int len; + + s--; + len = utf8_validate_cz(s); + if (len == 0) + goto failed; /* Invalid UTF-8 character. */ + + while (len--) + *b++ = *s++; + } + + /* + * Update sb to know about the new bytes, + * and set up b to write another character. + */ + if (out) { + sb.cur = b; + sb_need(&sb, 4); + b = sb.cur; + } else { + b = throwaway_buffer; + } + } + s++; + + if (out) + *out = sb_finish(&sb); + *sp = s; + return true; + +failed: + if (out) + sb_free(&sb); + return false; +} + +/* + * The JSON spec says that a number shall follow this precise pattern + * (spaces and quotes added for readability): + * '-'? (0 | [1-9][0-9]*) ('.' [0-9]+)? ([Ee] [+-]? [0-9]+)? + * + * However, some JSON parsers are more liberal. For instance, PHP accepts + * '.5' and '1.'. JSON.parse accepts '+3'. + * + * This function takes the strict approach. + */ +bool parse_number(const char **sp, double *out) +{ + const char *s = *sp; + + /* '-'? */ + if (*s == '-') + s++; + + /* (0 | [1-9][0-9]*) */ + if (*s == '0') { + s++; + } else { + if (!is_digit(*s)) + return false; + do { + s++; + } while (is_digit(*s)); + } + + /* ('.' [0-9]+)? */ + if (*s == '.') { + s++; + if (!is_digit(*s)) + return false; + do { + s++; + } while (is_digit(*s)); + } + + /* ([Ee] [+-]? [0-9]+)? */ + if (*s == 'E' || *s == 'e') { + s++; + if (*s == '+' || *s == '-') + s++; + if (!is_digit(*s)) + return false; + do { + s++; + } while (is_digit(*s)); + } + + if (out) + *out = strtod(*sp, NULL); + + *sp = s; + return true; +} + +static void skip_space(const char **sp) +{ + const char *s = *sp; + while (is_space(*s)) + s++; + *sp = s; +} + +static void emit_value(SB *out, const JsonNode *node) +{ + assert(tag_is_valid(node->tag)); + switch (node->tag) { + case JSON_NULL: + sb_puts(out, "null"); + break; + case JSON_BOOL: + sb_puts(out, node->bool_ ? "true" : "false"); + break; + case JSON_STRING: + emit_string(out, node->string_); + break; + case JSON_NUMBER: + emit_number(out, node->number_); + break; + case JSON_ARRAY: + emit_array(out, node); + break; + case JSON_OBJECT: + emit_object(out, node); + break; + default: + assert(false); + } +} + +void emit_value_indented(SB *out, const JsonNode *node, const char *space, int indent_level) +{ + assert(tag_is_valid(node->tag)); + switch (node->tag) { + case JSON_NULL: + sb_puts(out, "null"); + break; + case JSON_BOOL: + sb_puts(out, node->bool_ ? "true" : "false"); + break; + case JSON_STRING: + emit_string(out, node->string_); + break; + case JSON_NUMBER: + emit_number(out, node->number_); + break; + case JSON_ARRAY: + emit_array_indented(out, node, space, indent_level); + break; + case JSON_OBJECT: + emit_object_indented(out, node, space, indent_level); + break; + default: + assert(false); + } +} + +static void emit_array(SB *out, const JsonNode *array) +{ + const JsonNode *element; + + sb_putc(out, '['); + json_foreach(element, array) { + emit_value(out, element); + if (element->next != NULL) + sb_putc(out, ','); + } + sb_putc(out, ']'); +} + +static void emit_array_indented(SB *out, const JsonNode *array, const char *space, int indent_level) +{ + const JsonNode *element = array->children.head; + int i; + + if (element == NULL) { + sb_puts(out, "[]"); + return; + } + + sb_puts(out, "[\n"); + while (element != NULL) { + for (i = 0; i < indent_level + 1; i++) + sb_puts(out, space); + emit_value_indented(out, element, space, indent_level + 1); + + element = element->next; + sb_puts(out, element != NULL ? ",\n" : "\n"); + } + for (i = 0; i < indent_level; i++) + sb_puts(out, space); + sb_putc(out, ']'); +} + +static void emit_object(SB *out, const JsonNode *object) +{ + const JsonNode *member; + + sb_putc(out, '{'); + json_foreach(member, object) { + emit_string(out, member->key); + sb_putc(out, ':'); + emit_value(out, member); + if (member->next != NULL) + sb_putc(out, ','); + } + sb_putc(out, '}'); +} + +static void emit_object_indented(SB *out, const JsonNode *object, const char *space, int indent_level) +{ + const JsonNode *member = object->children.head; + int i; + + if (member == NULL) { + sb_puts(out, "{}"); + return; + } + + sb_puts(out, "{\n"); + while (member != NULL) { + for (i = 0; i < indent_level + 1; i++) + sb_puts(out, space); + emit_string(out, member->key); + sb_puts(out, ": "); + emit_value_indented(out, member, space, indent_level + 1); + + member = member->next; + sb_puts(out, member != NULL ? ",\n" : "\n"); + } + for (i = 0; i < indent_level; i++) + sb_puts(out, space); + sb_putc(out, '}'); +} + +void emit_string(SB *out, const char *str) +{ + bool escape_unicode = false; + const char *s = str; + char *b; + + assert(utf8_validate(str)); + + /* + * 14 bytes is enough space to write up to two + * \uXXXX escapes and two quotation marks. + */ + sb_need(out, 14); + b = out->cur; + + *b++ = '"'; + while (*s != 0) { + unsigned char c = *s++; + + /* Encode the next character, and write it to b. */ + switch (c) { + case '"': + *b++ = '\\'; + *b++ = '"'; + break; + case '\\': + *b++ = '\\'; + *b++ = '\\'; + break; + case '\b': + *b++ = '\\'; + *b++ = 'b'; + break; + case '\f': + *b++ = '\\'; + *b++ = 'f'; + break; + case '\n': + *b++ = '\\'; + *b++ = 'n'; + break; + case '\r': + *b++ = '\\'; + *b++ = 'r'; + break; + case '\t': + *b++ = '\\'; + *b++ = 't'; + break; + default: { + int len; + + s--; + len = utf8_validate_cz(s); + + if (len == 0) { + /* + * Handle invalid UTF-8 character gracefully in production + * by writing a replacement character (U+FFFD) + * and skipping a single byte. + * + * This should never happen when assertions are enabled + * due to the assertion at the beginning of this function. + */ + assert(false); + if (escape_unicode) { + strcpy(b, "\\uFFFD"); + b += 6; + } else { + *b++ = (char)0xEF; + *b++ = (char)0xBF; + *b++ = (char)0xBD; + } + s++; + } else if (c < 0x1F || (c >= 0x80 && escape_unicode)) { + /* Encode using \u.... */ + uint32_t unicode; + + s += utf8_read_char(s, &unicode); + + if (unicode <= 0xFFFF) { + *b++ = '\\'; + *b++ = 'u'; + b += write_hex16(b, unicode); + } else { + /* Produce a surrogate pair. */ + uint16_t uc, lc; + assert(unicode <= 0x10FFFF); + to_surrogate_pair(unicode, &uc, &lc); + *b++ = '\\'; + *b++ = 'u'; + b += write_hex16(b, uc); + *b++ = '\\'; + *b++ = 'u'; + b += write_hex16(b, lc); + } + } else { + /* Write the character directly. */ + while (len--) + *b++ = *s++; + } + + break; + } + } + + /* + * Update *out to know about the new bytes, + * and set up b to write another encoded character. + */ + out->cur = b; + sb_need(out, 14); + b = out->cur; + } + *b++ = '"'; + + out->cur = b; +} + +static void emit_number(SB *out, double num) +{ + /* + * This isn't exactly how JavaScript renders numbers, + * but it should produce valid JSON for reasonable numbers + * preserve precision well enough, and avoid some oddities + * like 0.3 -> 0.299999999999999988898 . + */ + char buf[64]; + sprintf(buf, "%.16g", num); + + if (number_is_valid(buf)) + sb_puts(out, buf); + else + sb_puts(out, "null"); +} + +static bool tag_is_valid(unsigned int tag) +{ + return (/* tag >= JSON_NULL && */ tag <= JSON_OBJECT); +} + +static bool number_is_valid(const char *num) +{ + return (parse_number(&num, NULL) && *num == '\0'); +} + +static bool expect_literal(const char **sp, const char *str) +{ + const char *s = *sp; + + while (*str != '\0') + if (*s++ != *str++) + return false; + + *sp = s; + return true; +} + +/* + * Parses exactly 4 hex characters (capital or lowercase). + * Fails if any input chars are not [0-9A-Fa-f]. + */ +static bool parse_hex16(const char **sp, uint16_t *out) +{ + const char *s = *sp; + uint16_t ret = 0; + uint16_t i; + uint16_t tmp; + char c; + + for (i = 0; i < 4; i++) { + c = *s++; + if (c >= '0' && c <= '9') + tmp = c - '0'; + else if (c >= 'A' && c <= 'F') + tmp = c - 'A' + 10; + else if (c >= 'a' && c <= 'f') + tmp = c - 'a' + 10; + else + return false; + + ret <<= 4; + ret += tmp; + } + + if (out) + *out = ret; + *sp = s; + return true; +} + +/* + * Encodes a 16-bit number into hexadecimal, + * writing exactly 4 hex chars. + */ +static int write_hex16(char *out, uint16_t val) +{ + const char *hex = "0123456789ABCDEF"; + + *out++ = hex[(val >> 12) & 0xF]; + *out++ = hex[(val >> 8) & 0xF]; + *out++ = hex[(val >> 4) & 0xF]; + *out++ = hex[ val & 0xF]; + + return 4; +} + +bool json_check(const JsonNode *node, char errmsg[256]) +{ + #define problem(...) do { \ + if (errmsg != NULL) \ + snprintf(errmsg, 256, __VA_ARGS__); \ + return false; \ + } while (0) + + if (node->key != NULL && !utf8_validate(node->key)) + problem("key contains invalid UTF-8"); + + if (!tag_is_valid(node->tag)) + problem("tag is invalid (%u)", node->tag); + + if (node->tag == JSON_BOOL) { + if (node->bool_ != false && node->bool_ != true) + problem("bool_ is neither false (%d) nor true (%d)", (int)false, (int)true); + } else if (node->tag == JSON_STRING) { + if (node->string_ == NULL) + problem("string_ is NULL"); + if (!utf8_validate(node->string_)) + problem("string_ contains invalid UTF-8"); + } else if (node->tag == JSON_ARRAY || node->tag == JSON_OBJECT) { + JsonNode *head = node->children.head; + JsonNode *tail = node->children.tail; + + if (head == NULL || tail == NULL) { + if (head != NULL) + problem("tail is NULL, but head is not"); + if (tail != NULL) + problem("head is NULL, but tail is not"); + } else { + JsonNode *child; + JsonNode *last = NULL; + + if (head->prev != NULL) + problem("First child's prev pointer is not NULL"); + + for (child = head; child != NULL; last = child, child = child->next) { + if (child == node) + problem("node is its own child"); + if (child->next == child) + problem("child->next == child (cycle)"); + if (child->next == head) + problem("child->next == head (cycle)"); + + if (child->parent != node) + problem("child does not point back to parent"); + if (child->next != NULL && child->next->prev != child) + problem("child->next does not point back to child"); + + if (node->tag == JSON_ARRAY && child->key != NULL) + problem("Array element's key is not NULL"); + if (node->tag == JSON_OBJECT && child->key == NULL) + problem("Object member's key is NULL"); + + if (!json_check(child, errmsg)) + return false; + } + + if (last != tail) + problem("tail does not match pointer found by starting at head and following next links"); + } + } + + return true; + + #undef problem +} diff --git a/contrib/ccan/json/json.h b/contrib/ccan/json/json.h new file mode 100644 index 0000000..6eef48a --- /dev/null +++ b/contrib/ccan/json/json.h @@ -0,0 +1,99 @@ +/* SPDX-License-Identifier: MIT + * Source: https://ccodearchive.net/info/json.html + * Copyright (C) 2011 Joseph A. Adams (joeyadams3.14159@gmail.com) */ + +#ifndef CCAN_JSON_H +#define CCAN_JSON_H + +#include <lib/defines.h> +#include <stdbool.h> +#include <stddef.h> + +typedef enum { + JSON_NULL, + JSON_BOOL, + JSON_STRING, + JSON_NUMBER, + JSON_ARRAY, + JSON_OBJECT, +} JsonTag; + +typedef struct JsonNode JsonNode; + +struct JsonNode +{ + /* only if parent is an object or array (NULL otherwise) */ + JsonNode *parent; + JsonNode *prev, *next; + + /* only if parent is an object (NULL otherwise) */ + char *key; /* Must be valid UTF-8. */ + + JsonTag tag; + union { + /* JSON_BOOL */ + bool bool_; + + /* JSON_STRING */ + char *string_; /* Must be valid UTF-8. */ + + /* JSON_NUMBER */ + double number_; + + /* JSON_ARRAY */ + /* JSON_OBJECT */ + struct { + JsonNode *head, *tail; + } children; + }; +}; + +/*** Encoding, decoding, and validation ***/ + +KR_EXPORT JsonNode *json_decode (const char *json); +KR_EXPORT char *json_encode (const JsonNode *node); +KR_EXPORT char *json_encode_string (const char *str); +KR_EXPORT char *json_stringify (const JsonNode *node, const char *space); +KR_EXPORT void json_delete (JsonNode *node); + +KR_EXPORT bool json_validate (const char *json); + +/*** Lookup and traversal ***/ + +KR_EXPORT JsonNode *json_find_element (JsonNode *array, int index); +KR_EXPORT JsonNode *json_find_member (JsonNode *object, const char *key); + +KR_EXPORT JsonNode *json_first_child (const JsonNode *node); + +#define json_foreach(i, object_or_array) \ + for ((i) = json_first_child(object_or_array); \ + (i) != NULL; \ + (i) = (i)->next) + +/*** Construction and manipulation ***/ + +KR_EXPORT JsonNode *json_mknull(void); +KR_EXPORT JsonNode *json_mkbool(bool b); +KR_EXPORT JsonNode *json_mkstring(const char *s); +KR_EXPORT JsonNode *json_mknumber(double n); +KR_EXPORT JsonNode *json_mkarray(void); +KR_EXPORT JsonNode *json_mkobject(void); + +KR_EXPORT void json_append_element(JsonNode *array, JsonNode *element); +KR_EXPORT void json_prepend_element(JsonNode *array, JsonNode *element); +KR_EXPORT void json_append_member(JsonNode *object, const char *key, JsonNode *value); +KR_EXPORT void json_prepend_member(JsonNode *object, const char *key, JsonNode *value); + +KR_EXPORT void json_remove_from_parent(JsonNode *node); + +/*** Debugging ***/ + +/* + * Look for structure and encoding problems in a JsonNode or its descendents. + * + * If a problem is detected, return false, writing a description of the problem + * to errmsg (unless errmsg is NULL). + */ +KR_EXPORT bool json_check(const JsonNode *node, char errmsg[256]); + +#endif diff --git a/contrib/ccan/json/json.spdx b/contrib/ccan/json/json.spdx new file mode 100644 index 0000000..9943583 --- /dev/null +++ b/contrib/ccan/json/json.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: ccan-json +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-d9b4db4c-062f-4add-89b6-f603224f5a2c + +PackageName: json +PackageDownloadLocation: git+https://github.com/rustyrussell/ccan@f4eb3a18caf946ee6cc2cb57e2a0c6a6f115157f#ccan/json +PackageOriginator: Person: Joseph A. Adams (joeyadams3.14159@gmail.com) +PackageLicenseDeclared: MIT diff --git a/contrib/cleanup.h b/contrib/cleanup.h new file mode 100644 index 0000000..7d6cdbe --- /dev/null +++ b/contrib/cleanup.h @@ -0,0 +1,25 @@ +/* Copyright (C) 2015-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later +*/ +/** + * Cleanup attributes. + * @cond internal + */ +#pragma once +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> + +#define auto_free __attribute__((cleanup(_cleanup_free))) +static inline void _cleanup_free(const void *p) { + free(*(char **)p); +} +#define auto_close __attribute__((cleanup(_cleanup_close))) +static inline void _cleanup_close(int *p) { + if (*p != -1) close(*p); +} +#define auto_fclose __attribute__((cleanup(_cleanup_fclose))) +static inline void _cleanup_fclose(FILE **p) { + if (*p) fclose(*p); +} +/* @endcond */ diff --git a/contrib/config.h b/contrib/config.h new file mode 100644 index 0000000..336511f --- /dev/null +++ b/contrib/config.h @@ -0,0 +1,7 @@ +/* Dummy file, no real configuration here + * SPDX-License-Identifier: GPL-3.0-or-later */ +#define HAVE_ATTRIBUTE_COLD 1 +#define HAVE_ATTRIBUTE_NORETURN 1 +#define HAVE_ATTRIBUTE_PURE 1 +#define HAVE_ATTRIBUTE_UNUSED 1 +#define HAVE_ATTRIBUTE_NONNULL 1 diff --git a/contrib/dynarray.h b/contrib/dynarray.h new file mode 100644 index 0000000..34c74f8 --- /dev/null +++ b/contrib/dynarray.h @@ -0,0 +1,112 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ + +/*! + * \brief Simple write-once allocation-optimal dynamic array. + * + * Include it into your .c file + * + * prefix - identifier prefix, e.g. ptr -> struct ptr_dynarray, ptr_dynarray_add(), ... + * ntype - data type to be stored. Let it be a number, pointer or small struct + * initial_capacity - how many data items will be allocated on stac and copied with assignment + * + * prefix_dynarray_add() - add a data item + * prefix_dynarray_fix() - call EVERYTIME the array is copied from some already invalid stack + * prefix_dynarray_free() - call EVERYTIME you dismiss all copies of the array + * + */ + +#include <stdlib.h> +#include <assert.h> + +#pragma once + +#define DYNARRAY_VISIBILITY_STATIC static +#define DYNARRAY_VISIBILITY_PUBLIC +#define DYNARRAY_VISIBILITY_LIBRARY __public__ + +#define dynarray_declare(prefix, ntype, visibility, initial_capacity) \ + typedef struct prefix ## _dynarray { \ + ssize_t capacity; \ + ssize_t size; \ + ntype *(*arr)(struct prefix ## _dynarray *dynarray); \ + ntype init[initial_capacity]; \ + ntype *_arr; \ + } prefix ## _dynarray_t; \ + \ + visibility ntype *prefix ## _dynarray_arr(prefix ## _dynarray_t *dynarray); \ + visibility void prefix ## _dynarray_add(prefix ## _dynarray_t *dynarray, \ + ntype const *to_add); \ + visibility void prefix ## _dynarray_free(prefix ## _dynarray_t *dynarray); + +#define dynarray_foreach(prefix, ntype, ptr, array) \ + for (ntype *ptr = prefix ## _dynarray_arr(&(array)); \ + ptr < prefix ## _dynarray_arr(&(array)) + (array).size; ptr++) + +#define dynarray_define(prefix, ntype, visibility) \ + \ + static void prefix ## _dynarray_free__(struct prefix ## _dynarray *dynarray) \ + { \ + if (dynarray->capacity > sizeof(dynarray->init) / sizeof(*dynarray->init)) { \ + free(dynarray->_arr); \ + } \ + } \ + \ + __attribute__((unused)) \ + visibility ntype *prefix ## _dynarray_arr(struct prefix ## _dynarray *dynarray) \ + { \ + assert(dynarray->size <= dynarray->capacity); \ + return (dynarray->capacity <= sizeof(dynarray->init) / sizeof(*dynarray->init) ? \ + dynarray->init : dynarray->_arr); \ + } \ + \ + static ntype *prefix ## _dynarray_arr_init__(struct prefix ## _dynarray *dynarray) \ + { \ + assert(dynarray->capacity == sizeof(dynarray->init) / sizeof(*dynarray->init)); \ + return dynarray->init; \ + } \ + \ + static ntype *prefix ## _dynarray_arr_arr__(struct prefix ## _dynarray *dynarray) \ + { \ + assert(dynarray->capacity > sizeof(dynarray->init) / sizeof(*dynarray->init)); \ + return dynarray->_arr; \ + } \ + \ + __attribute__((unused)) \ + visibility void prefix ## _dynarray_add(struct prefix ## _dynarray *dynarray, \ + ntype const *to_add) \ + { \ + if (dynarray->capacity < 0) { \ + return; \ + } \ + if (dynarray->capacity == 0) { \ + dynarray->capacity = sizeof(dynarray->init) / sizeof(*dynarray->init); \ + dynarray->arr = prefix ## _dynarray_arr_init__; \ + } \ + if (dynarray->size >= dynarray->capacity) { \ + ssize_t new_capacity = dynarray->capacity * 2 + 1; \ + ntype *new_arr = calloc(new_capacity, sizeof(ntype)); \ + if (new_arr == NULL) { \ + prefix ## _dynarray_free__(dynarray); \ + dynarray->capacity = dynarray->size = -1; \ + return; \ + } \ + if (dynarray->capacity > 0) { \ + memcpy(new_arr, prefix ## _dynarray_arr(dynarray), \ + dynarray->capacity * sizeof(ntype)); \ + } \ + prefix ## _dynarray_free__(dynarray); \ + dynarray->_arr = new_arr; \ + dynarray->capacity = new_capacity; \ + dynarray->arr = prefix ## _dynarray_arr_arr__; \ + } \ + prefix ## _dynarray_arr(dynarray)[dynarray->size++] = *to_add; \ + } \ + \ + __attribute__((unused)) \ + visibility void prefix ## _dynarray_free(struct prefix ## _dynarray *dynarray) \ + { \ + prefix ## _dynarray_free__(dynarray); \ + memset(dynarray, 0, sizeof(*dynarray)); \ + } diff --git a/contrib/dynarray.spdx b/contrib/dynarray.spdx new file mode 100644 index 0000000..02911c9 --- /dev/null +++ b/contrib/dynarray.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: knotdns-dynarray +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-ce6423dd-ac6a-4e78-90c3-5cbdef1e252c + +PackageName: knotdns-dynarray +PackageDownloadLocation: git+https://gitlab.nic.cz/knot/knot-dns.git@48c8b4f38cf5f7bf505c79b56adf7580688f6d3d#src/contrib/dynarray.h +PackageOriginator: Organization: Knot DNS contributors +PackageLicenseDeclared: GPL-3.0-or-later diff --git a/contrib/licenses/BSD-MIT b/contrib/licenses/BSD-MIT new file mode 100644 index 0000000..6e50b00 --- /dev/null +++ b/contrib/licenses/BSD-MIT @@ -0,0 +1,21 @@ +SPDX-License-Identifier: MIT +SPDX-URL: https://spdx.org/licenses/MIT.html +License-Text: + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/contrib/licenses/CC0 b/contrib/licenses/CC0 new file mode 100644 index 0000000..937f712 --- /dev/null +++ b/contrib/licenses/CC0 @@ -0,0 +1,32 @@ +SPDX-License-Identifier: CC0-1.0 +SPDX-URL: https://spdx.org/licenses/CC0-1.0.html +License-Text: + +Statement of Purpose + +The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work"). + +Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others. + +For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights. + +1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following: + + the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work; + moral rights retained by the original author(s) and/or performer(s); + publicity and privacy rights pertaining to a person's image or likeness depicted in a Work; + rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below; + rights protecting the extraction, dissemination, use and reuse of data in a Work; + database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and + other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof. + +2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose. + +3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose. + +4. Limitations and Disclaimers. + + No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document. + Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law. + Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work. + Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work. diff --git a/contrib/licenses/LGPL2 b/contrib/licenses/LGPL2 new file mode 100644 index 0000000..682170d --- /dev/null +++ b/contrib/licenses/LGPL2 @@ -0,0 +1,506 @@ +SPDX-License-Identifier: LGPL-2.1-or-later +SPDX-URL: http://spdx.org/licenses/LGPL-2.1 +License-Text: + + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! diff --git a/contrib/mempattern.c b/contrib/mempattern.c new file mode 100644 index 0000000..ae3bd6f --- /dev/null +++ b/contrib/mempattern.c @@ -0,0 +1,151 @@ +/* Copyright (C) 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +#include <stdlib.h> + +#include "contrib/mempattern.h" +#include "contrib/ucw/mempool.h" + +static void mm_nofree(void *p) +{ + /* nop */ +} + +static void *mm_malloc(void *ctx, size_t n) +{ + (void)ctx; + return malloc(n); +} + +void *mm_alloc(knot_mm_t *mm, size_t size) +{ + if (mm) { + return mm->alloc(mm->ctx, size); + } else { + return malloc(size); + } +} + +void *mm_calloc(knot_mm_t *mm, size_t nmemb, size_t size) +{ + if (nmemb == 0 || size == 0) { + return NULL; + } + if (mm) { + size_t total_size = nmemb * size; + if (total_size / nmemb != size) { // Overflow check + return NULL; + } + void *mem = mm_alloc(mm, total_size); + if (mem == NULL) { + return NULL; + } + return memset(mem, 0, total_size); + } else { + return calloc(nmemb, size); + } +} + +void *mm_realloc(knot_mm_t *mm, void *what, size_t size, size_t prev_size) +{ + if (mm) { + void *p = mm->alloc(mm->ctx, size); + if (p == NULL) { + return NULL; + } else { + if (what) { + memcpy(p, what, + prev_size < size ? prev_size : size); + } + mm_free(mm, what); + return p; + } + } else { + return realloc(what, size); + } +} + +char *mm_strdup(knot_mm_t *mm, const char *s) +{ + if (s == NULL) { + return NULL; + } + if (mm) { + size_t len = strlen(s) + 1; + void *mem = mm_alloc(mm, len); + if (mem == NULL) { + return NULL; + } + return memcpy(mem, s, len); + } else { + return strdup(s); + } +} + +void mm_free(knot_mm_t *mm, void *what) +{ + if (mm) { + if (mm->free) { + mm->free(what); + } + } else { + free(what); + } +} + +void mm_ctx_init(knot_mm_t *mm) +{ + mm->ctx = NULL; + mm->alloc = mm_malloc; + mm->free = free; +} + +void mm_ctx_mempool(knot_mm_t *mm, size_t chunk_size) +{ + mm->ctx = mp_new(chunk_size); + mm->alloc = (knot_mm_alloc_t)mp_alloc; + mm->free = mm_nofree; +} + + +/* Code in addition to Knot's mempattern. */ + +void *mm_malloc_aligned(void *ctx, size_t n) +{ + size_t alignment = (size_t)ctx; + void *res; + int err = posix_memalign(&res, alignment, n); + if (err == 0) { + return res; + } else { + assert(err == -1 && errno == ENOMEM); + return NULL; + } +} + +knot_mm_t * mm_ctx_mempool2(size_t chunk_size) +{ + knot_mm_t pool_tmp; + mm_ctx_mempool(&pool_tmp, chunk_size); + knot_mm_t *pool = mm_alloc(&pool_tmp, sizeof(*pool)); + if (!pool) { + mp_delete(pool_tmp.ctx); + return NULL; + } + memcpy(pool, &pool_tmp, sizeof(*pool)); + return pool; +} + diff --git a/contrib/mempattern.h b/contrib/mempattern.h new file mode 100644 index 0000000..0b9957b --- /dev/null +++ b/contrib/mempattern.h @@ -0,0 +1,83 @@ +/* Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + */ + +/*! + * \brief Memory allocation related functions. + */ + +#pragma once + +#include <libknot/mm_ctx.h> +#include "lib/defines.h" +#include <assert.h> +#include <stdint.h> + +/*! \brief Default memory block size. */ +#define MM_DEFAULT_BLKSIZE 4096 + +/*! \brief Allocs using 'mm' if any, uses system malloc() otherwise. */ +KR_EXPORT +void *mm_alloc(knot_mm_t *mm, size_t size); + +/*! \brief Callocs using 'mm' if any, uses system calloc() otherwise. */ +void *mm_calloc(knot_mm_t *mm, size_t nmemb, size_t size); + +/*! \brief Reallocs using 'mm' if any, uses system realloc() otherwise. */ +KR_EXPORT +void *mm_realloc(knot_mm_t *mm, void *what, size_t size, size_t prev_size); + +/*! \brief Strdups using 'mm' if any, uses system strdup() otherwise. */ +char *mm_strdup(knot_mm_t *mm, const char *s); + +/*! \brief Free using 'mm' if any, uses system free() otherwise. */ +KR_EXPORT +void mm_free(knot_mm_t *mm, void *what); + +/*! \brief Initialize default memory allocation context. */ +void mm_ctx_init(knot_mm_t *mm); + +/*! \brief Memory pool context. */ +void mm_ctx_mempool(knot_mm_t *mm, size_t chunk_size); + + +/* API in addition to Knot's mempattern. */ + +/*! \brief Readability: avoid const-casts in code. */ +static inline void free_const(const void *what) +{ + free((void *)what); +} + +/*! \brief posix_memalign() wrapper. */ +void *mm_malloc_aligned(void *ctx, size_t n); + +/*! \brief Initialize mm with malloc+free with specified alignment (a power of two). */ +static inline void mm_ctx_init_aligned(knot_mm_t *mm, size_t alignment) +{ + assert(__builtin_popcount(alignment) == 1); + mm_ctx_init(mm); + mm->ctx = (uint8_t *)NULL + alignment; /*< roundabout to satisfy linters */ + /* posix_memalign() doesn't allow alignment < sizeof(void*), + * and there's no point in using it for small values anyway, + * as plain malloc() guarantees at least max_align_t. */ + if (alignment > sizeof(max_align_t)) { + mm->alloc = mm_malloc_aligned; + } +} + +/*! \brief New memory pool context, allocated on itself. */ +KR_EXPORT knot_mm_t * mm_ctx_mempool2(size_t chunk_size); + diff --git a/contrib/meson.build b/contrib/meson.build new file mode 100644 index 0000000..5d97e88 --- /dev/null +++ b/contrib/meson.build @@ -0,0 +1,28 @@ +# contrib +# SPDX-License-Identifier: GPL-3.0-or-later + +contrib_src = files([ + 'ccan/asprintf/asprintf.c', + 'ccan/json/json.c', + 'ucw/mempool.c', + 'ucw/mempool-fmt.c', + 'mempattern.c', + 'murmurhash3/murmurhash3.c', + 'base32hex.c', + 'base64.c', + 'base64url.c' +]) + +contrib_inc = include_directories('.', '..') + +contrib_lib = static_library( + 'contrib', + contrib_src, + include_directories: contrib_inc, + dependencies: libknot, +) + +contrib_dep = declare_dependency( + include_directories: contrib_inc, + link_with: contrib_lib, +) diff --git a/contrib/murmurhash3/LICENSE b/contrib/murmurhash3/LICENSE new file mode 120000 index 0000000..fe25b01 --- /dev/null +++ b/contrib/murmurhash3/LICENSE @@ -0,0 +1 @@ +../licenses/CC0
\ No newline at end of file diff --git a/contrib/murmurhash3/murmurhash3.c b/contrib/murmurhash3/murmurhash3.c new file mode 100644 index 0000000..995c236 --- /dev/null +++ b/contrib/murmurhash3/murmurhash3.c @@ -0,0 +1,77 @@ +/* This is MurmurHash3. The original C++ code was placed in the public domain + * by its author, Austin Appleby. + * + * SPDX-License-Identifier: CC0-1.0 + * Source: https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp */ + +#include "murmurhash3.h" +#include "string.h" + +static inline uint32_t fmix(uint32_t h) +{ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + + return h; +} + +static inline uint32_t rotl32(uint32_t x, int8_t r) +{ + return (x << r) | (x >> (32 - r)); +} + +uint32_t hash(const char* data, size_t len_) +{ + const int len = (int) len_; + const int nblocks = len / 4; + + uint32_t h1 = 0xc062fb4a; + + uint32_t c1 = 0xcc9e2d51; + uint32_t c2 = 0x1b873593; + + //---------- + // body + + int i; + for(i = -nblocks; i; i++) + { + uint32_t k1; + memcpy(&k1, data + nblocks * 4 + i * sizeof(k1), sizeof(k1)); + + k1 *= c1; + k1 = rotl32(k1, 15); + k1 *= c2; + + h1 ^= k1; + h1 = rotl32(h1, 13); + h1 = h1*5+0xe6546b64; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*4); + + uint32_t k1 = 0; + + switch(len & 3) + { + case 3: k1 ^= tail[2] << 16; + case 2: k1 ^= tail[1] << 8; + case 1: k1 ^= tail[0]; + k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1; + } + + //---------- + // finalization + + h1 ^= len; + + h1 = fmix(h1); + + return h1; +} diff --git a/contrib/murmurhash3/murmurhash3.h b/contrib/murmurhash3/murmurhash3.h new file mode 100644 index 0000000..d849961 --- /dev/null +++ b/contrib/murmurhash3/murmurhash3.h @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: CC0-1.0 + * Source: https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp */ + +#pragma once + +#include <stdlib.h> +#include <stdint.h> + +uint32_t hash(const char* data, size_t len); diff --git a/contrib/murmurhash3/murmurhash3.spdx b/contrib/murmurhash3/murmurhash3.spdx new file mode 100644 index 0000000..7ce5a54 --- /dev/null +++ b/contrib/murmurhash3/murmurhash3.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: ccan-json +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-d9b4db4c-062f-4add-89b6-f603224f5a2c + +PackageName: json +PackageDownloadLocation: git+https://github.com/aappleby/smhasher.git@73e075b203d9c76cd1e20d6c8907c2983d653f33#MurmurHash3.cpp +PackageOriginator: Person: Austin Appleby (aappleby@gmail.com) +PackageLicenseDeclared: CC0-1.0 diff --git a/contrib/ucw/LICENSE b/contrib/ucw/LICENSE new file mode 120000 index 0000000..0cb7f47 --- /dev/null +++ b/contrib/ucw/LICENSE @@ -0,0 +1 @@ +../licenses/LGPL2
\ No newline at end of file diff --git a/contrib/ucw/alloc.h b/contrib/ucw/alloc.h new file mode 100644 index 0000000..4b5440b --- /dev/null +++ b/contrib/ucw/alloc.h @@ -0,0 +1,38 @@ +/* + * UCW Library -- Generic allocators + * + * (c) 2014 Martin Mares <mj@ucw.cz> + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#ifndef _UCW_ALLOC_H +#define _UCW_ALLOC_H + +/** + * This structure describes a generic allocator. It provides pointers + * to three functions, which handle the actual (re)allocations. + **/ +struct ucw_allocator { + void * (*alloc)(struct ucw_allocator *alloc, size_t size); + void * (*realloc)(struct ucw_allocator *alloc, void *ptr, size_t old_size, size_t new_size); + void (*free)(struct ucw_allocator *alloc, void *ptr); +}; + +/* alloc-std.c */ + +/** + * [[std]] + * This allocator uses <<basics:xmalloc()>>, <<basics:xrealloc()>> and <<basics:xfree()>>. The memory + * it allocates is left unitialized. + **/ +extern struct ucw_allocator ucw_allocator_std; + +/** + * [[zeroing]] + * This allocator uses <<basics:xmalloc()>>, <<basics:xrealloc()>> and <<basics:xfree()>>. All memory + * is zeroed upon allocation. + **/ +extern struct ucw_allocator ucw_allocator_zeroed; + +#endif diff --git a/contrib/ucw/config.h b/contrib/ucw/config.h new file mode 100644 index 0000000..3c94104 --- /dev/null +++ b/contrib/ucw/config.h @@ -0,0 +1,58 @@ +/* + * UCW Library -- Configuration-Dependent Definitions + * + * (c) 1997--2012 Martin Mares <mj@ucw.cz> + * (c) 2006 Robert Spalek <robert@ucw.cz> + * + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#ifndef _UCW_CONFIG_H +#define _UCW_CONFIG_H + +/* Default page size and pointer alignment */ +#ifndef CPU_PAGE_SIZE +#define CPU_PAGE_SIZE 4096 +#endif +#define CPU_STRUCT_ALIGN sizeof(void *) + +/* Tell libc we're going to use all extensions available */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +/* Types (based on standard C99 integers) */ + +#include <stddef.h> +#include <stdint.h> + +typedef uint8_t byte; /** Exactly 8 bits, unsigned **/ +typedef uint8_t u8; /** Exactly 8 bits, unsigned **/ +typedef int8_t s8; /** Exactly 8 bits, signed **/ +typedef uint16_t u16; /** Exactly 16 bits, unsigned **/ +typedef int16_t s16; /** Exactly 16 bits, signed **/ +typedef uint32_t u32; /** Exactly 32 bits, unsigned **/ +typedef int32_t s32; /** Exactly 32 bits, signed **/ +typedef uint64_t u64; /** Exactly 64 bits, unsigned **/ +typedef int64_t s64; /** Exactly 64 bits, signed **/ + + +#ifndef uint /* Redefining typedef is a C11 feature. */ +typedef unsigned int uint; /** A better pronounceable alias for `unsigned int` **/ +#define uint uint +#endif + +typedef s64 timestamp_t; /** Milliseconds since an unknown epoch **/ + +// FIXME: This should be removed soon +typedef uint uns; /** Backwards compatible alias for `uint' ***/ + +#ifdef CONFIG_UCW_LARGE_FILES +typedef s64 ucw_off_t; /** File position (either 32- or 64-bit, depending on `CONFIG_UCW_LARGE_FILES`). **/ +#else +typedef s32 ucw_off_t; +#endif + +#endif diff --git a/contrib/ucw/lib.h b/contrib/ucw/lib.h new file mode 100644 index 0000000..89b3a20 --- /dev/null +++ b/contrib/ucw/lib.h @@ -0,0 +1,125 @@ +/* + * The UCW Library -- Miscellaneous Functions + * + * (c) 1997--2014 Martin Mares <mj@ucw.cz> + * (c) 2005--2014 Tomas Valla <tom@ucw.cz> + * (c) 2006 Robert Spalek <robert@ucw.cz> + * (c) 2007 Pavel Charvat <pchar@ucw.cz> + * + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#ifndef _UCW_LIB_H +#define _UCW_LIB_H + +#include <stdarg.h> +#include <stdbool.h> +#include <stdlib.h> + +#ifdef CONFIG_UCW_CLEAN_ABI +#define assert_failed ucw_assert_failed +#define assert_failed_msg ucw_assert_failed_msg +#define assert_failed_noinfo ucw_assert_failed_noinfo +#define big_alloc ucw_big_alloc +#define big_alloc_zero ucw_big_alloc_zero +#define big_free ucw_big_free +#define die ucw_die +#define log_die_hook ucw_log_die_hook +#define log_file ucw_log_file +#define log_fork ucw_log_fork +#define log_init ucw_log_init +#define log_pid ucw_log_pid +#define log_title ucw_log_title +#define msg ucw_msg +#define page_alloc ucw_page_alloc +#define page_alloc_zero ucw_page_alloc_zero +#define page_free ucw_page_free +#define page_realloc ucw_page_realloc +#define random_max ucw_random_max +#define random_max_u64 ucw_random_max_u64 +#define random_u32 ucw_random_u32 +#define random_u64 ucw_random_u64 +#define vdie ucw_vdie +#define vmsg ucw_vmsg +#define xfree ucw_xfree +#define xmalloc ucw_xmalloc +#define xmalloc_zero ucw_xmalloc_zero +#define xrealloc ucw_xrealloc +#define xstrdup ucw_xstrdup +#endif + +/*** === Macros for handling structures, offsets and alignment ***/ + +#define CHECK_PTR_TYPE(x, type) ((x)-(type)(x) + (type)(x)) /** Check that a pointer @x is of type @type. Fail compilation if not. **/ +#define PTR_TO(s, i) &((s*)0)->i /** Return OFFSETOF() in form of a pointer. **/ +#define OFFSETOF(s, i) ((uint)offsetof(s, i)) /** Offset of item @i from the start of structure @s **/ +#define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i))) /** Given a pointer @p to item @i of structure @s, return a pointer to the start of the struct. **/ + +/** Align an integer @s to the nearest higher multiple of @a (which should be a power of two) **/ +#define ALIGN_TO(s, a) (((s)+a-1)&~(a-1)) + +/** Align a pointer @p to the nearest higher multiple of @s. **/ +#define ALIGN_PTR(p, s) ((uintptr_t)(p) % (s) ? (typeof(p))((uintptr_t)(p) + (s) - (uintptr_t)(p) % (s)) : (p)) + +#define UNALIGNED_PART(ptr, type) (((uintptr_t) (ptr)) % sizeof(type)) + +/*** === Other utility macros ***/ + +#define MIN(a,b) (((a)<(b))?(a):(b)) /** Minimum of two numbers **/ +#define MAX(a,b) (((a)>(b))?(a):(b)) /** Maximum of two numbers **/ +#define CLAMP(x,min,max) ({ typeof(x) _t=x; (_t < min) ? min : (_t > max) ? max : _t; }) /** Clip a number @x to interval [@min,@max] **/ +#define ABS(x) ((x) < 0 ? -(x) : (x)) /** Absolute value **/ +#define ARRAY_SIZE(a) (sizeof(a)/sizeof(*(a))) /** The number of elements of an array **/ +#define STRINGIFY(x) #x /** Convert macro parameter to a string **/ +#define STRINGIFY_EXPANDED(x) STRINGIFY(x) /** Convert an expanded macro parameter to a string **/ +#define GLUE(x,y) x##y /** Glue two tokens together **/ +#define GLUE_(x,y) x##_##y /** Glue two tokens together, separating them by an underscore **/ + +#define COMPARE(x,y) do { if ((x)<(y)) return -1; if ((x)>(y)) return 1; } while(0) /** Numeric comparison function for qsort() **/ +#define REV_COMPARE(x,y) COMPARE(y,x) /** Reverse numeric comparison **/ +#define COMPARE_LT(x,y) do { if ((x)<(y)) return 1; if ((x)>(y)) return 0; } while(0) +#define COMPARE_GT(x,y) COMPARE_LT(y,x) + +#define ROL(x, bits) (((x) << (bits)) | ((uint)(x) >> (sizeof(uint)*8 - (bits)))) /** Bitwise rotation of an unsigned int to the left **/ +#define ROR(x, bits) (((uint)(x) >> (bits)) | ((x) << (sizeof(uint)*8 - (bits)))) /** Bitwise rotation of an unsigned int to the right **/ + +/*** === Shortcuts for GCC Extensions ***/ + +#ifdef __GNUC__ + +#include "ccan/compiler/compiler.h" +#define FORMAT_CHECK(x,y,z) __attribute__((format(x,y,z))) /** Checking of printf-like format strings **/ +#define likely(x) __builtin_expect((x),1) /** Use `if (likely(@x))` if @x is almost always true **/ +#define unlikely(x) __builtin_expect((x),0) /** Use `if (unlikely(@x))` to hint that @x is almost always false **/ + +#if __GNUC__ >= 4 || __GNUC__ == 3 && __GNUC_MINOR__ >= 3 +#define ALWAYS_INLINE inline __attribute__((always_inline)) /** Forcibly inline **/ +#define NO_INLINE __attribute__((noinline)) /** Forcibly uninline **/ +#else +#define ALWAYS_INLINE inline +#endif + +#if __GNUC__ >= 4 +#define LIKE_MALLOC __attribute__((malloc)) /** Function returns a "new" pointer **/ +#define SENTINEL_CHECK __attribute__((sentinel)) /** The last argument must be NULL **/ +#else +#define LIKE_MALLOC +#define SENTINEL_CHECK +#endif + +#else +#error This program requires the GNU C compiler. +#endif + +/*** + * [[logging]] + * + * === Basic logging functions (see <<log:,Logging>> and <ucw/log.h> for more) + ***/ + +#define DBG(x, ...) do { } while(0) +#define DBG_SPOT do { } while(0) +#define ASSERT(x) + +#endif diff --git a/contrib/ucw/libucw.spdx b/contrib/ucw/libucw.spdx new file mode 100644 index 0000000..e18b2ea --- /dev/null +++ b/contrib/ucw/libucw.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: libucw +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-c3d39e26-6b71-46d4-88ea-e52750932ff3 + +PackageName: libucw +PackageDownloadLocation: git://git.ucw.cz/libucw.git@f1bde7104b04d5254d1d1d7dcc8de790a43a416f#ucw/ +PackageOriginator: Organization: United Computer Wizards +PackageLicenseDeclared: LGPL-2.1-or-later diff --git a/contrib/ucw/mempool-fmt.c b/contrib/ucw/mempool-fmt.c new file mode 100644 index 0000000..22f3a50 --- /dev/null +++ b/contrib/ucw/mempool-fmt.c @@ -0,0 +1,99 @@ +/* + * UCW Library -- Memory Pools (Formatting) + * + * (c) 2005 Martin Mares <mj@ucw.cz> + * (c) 2007 Pavel Charvat <pchar@ucw.cz> + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#include <ucw/lib.h> +#include <ucw/mempool.h> + +#include <stdio.h> +#include <string.h> + +/* FIXME: migrate to Knot DNS version of mempools. */ +#pragma GCC diagnostic ignored "-Wpointer-arith" + +static char * +mp_vprintf_at(struct mempool *mp, size_t ofs, const char *fmt, va_list args) +{ + char *ret = mp_grow(mp, ofs + 1) + ofs; + va_list args2; + va_copy(args2, args); + int cnt = vsnprintf(ret, mp_avail(mp) - ofs, fmt, args2); + va_end(args2); + if (cnt < 0) + { + /* Our C library doesn't support C99 return value of vsnprintf, so we need to iterate */ + do + { + ret = mp_expand(mp) + ofs; + va_copy(args2, args); + cnt = vsnprintf(ret, mp_avail(mp) - ofs, fmt, args2); + va_end(args2); + } + while (cnt < 0); + } + else if ((uint)cnt >= mp_avail(mp) - ofs) + { + ret = mp_grow(mp, ofs + cnt + 1) + ofs; + va_copy(args2, args); + vsnprintf(ret, cnt + 1, fmt, args2); + va_end(args2); + } + mp_end(mp, ret + cnt + 1); + return ret - ofs; +} + +char * +mp_vprintf(struct mempool *mp, const char *fmt, va_list args) +{ + mp_start(mp, 1); + return mp_vprintf_at(mp, 0, fmt, args); +} + +char * +mp_printf(struct mempool *p, const char *fmt, ...) +{ + va_list args; + va_start(args, fmt); + char *res = mp_vprintf(p, fmt, args); + va_end(args); + return res; +} + +char * +mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args) +{ + size_t ofs = mp_open(mp, ptr); + ASSERT(ofs && !ptr[ofs - 1]); + return mp_vprintf_at(mp, ofs - 1, fmt, args); +} + +char * +mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) +{ + va_list args; + va_start(args, fmt); + char *res = mp_vprintf_append(mp, ptr, fmt, args); + va_end(args); + return res; +} + +#ifdef TEST + +int main(void) +{ + struct mempool *mp = mp_new(64); + char *x = mp_printf(mp, "<Hello, %s!>", "World"); + fputs(x, stdout); + x = mp_printf_append(mp, x, "<Appended>"); + fputs(x, stdout); + x = mp_printf(mp, "<Hello, %50s!>\n", "World"); + fputs(x, stdout); + return 0; +} + +#endif diff --git a/contrib/ucw/mempool.c b/contrib/ucw/mempool.c new file mode 100644 index 0000000..314b58e --- /dev/null +++ b/contrib/ucw/mempool.c @@ -0,0 +1,601 @@ +/* + * UCW Library -- Memory Pools (One-Time Allocation) + * + * (c) 1997--2014 Martin Mares <mj@ucw.cz> + * (c) 2007--2015 Pavel Charvat <pchar@ucw.cz> + * + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#undef LOCAL_DEBUG + +#include <ucw/config.h> +#include <ucw/lib.h> +#include <ucw/alloc.h> +#include <ucw/mempool.h> + +#include <string.h> +#include <stdlib.h> + +/* FIXME: migrate to Knot DNS version of mempools. */ +#pragma GCC diagnostic ignored "-Wpointer-arith" + +#define MP_CHUNK_TAIL ALIGN_TO(sizeof(struct mempool_chunk), CPU_STRUCT_ALIGN) +#define MP_SIZE_MAX (SIZE_MAX - MP_CHUNK_TAIL - CPU_PAGE_SIZE) + +struct mempool_chunk { +#ifdef CONFIG_DEBUG + struct mempool *pool; // Can be useful when analysing coredump for memory leaks +#endif + struct mempool_chunk *next; + size_t size; +}; + +static size_t +mp_align_size(size_t size) +{ +#ifdef CONFIG_UCW_POOL_IS_MMAP + size = MAX(size, 64 + MP_CHUNK_TAIL); + return ALIGN_TO(size, CPU_PAGE_SIZE) - MP_CHUNK_TAIL; +#else + return ALIGN_TO(size, CPU_STRUCT_ALIGN); +#endif +} + +static void *mp_allocator_alloc(struct ucw_allocator *a, size_t size) +{ + struct mempool *mp = (struct mempool *) a; + return mp_alloc_fast(mp, size); +} + +static void *mp_allocator_realloc(struct ucw_allocator *a, void *ptr, size_t old_size, size_t new_size) +{ + if (new_size <= old_size) + return ptr; + + /* + * In the future, we might want to do something like mp_realloc(), + * but we have to check that it is indeed the last block in the pool. + */ + struct mempool *mp = (struct mempool *) a; + void *new = mp_alloc_fast(mp, new_size); + memcpy(new, ptr, old_size); + return new; +} + +static void mp_allocator_free(struct ucw_allocator *a UNUSED, void *ptr UNUSED) +{ + // Does nothing +} + +void +mp_init(struct mempool *pool, size_t chunk_size) +{ + chunk_size = mp_align_size(MAX(sizeof(struct mempool), chunk_size)); + *pool = (struct mempool) { + .allocator = { + .alloc = mp_allocator_alloc, + .realloc = mp_allocator_realloc, + .free = mp_allocator_free, + }, + .chunk_size = chunk_size, + .threshold = chunk_size >> 1, + .last_big = &pool->last_big + }; +} + +static void * +mp_new_big_chunk(struct mempool *pool, size_t size) +{ + struct mempool_chunk *chunk; + chunk = malloc(size + MP_CHUNK_TAIL); + if (!chunk) + return NULL; + chunk = (struct mempool_chunk *)((char *)chunk + size); + chunk->size = size; + if (pool) + pool->total_size += size + MP_CHUNK_TAIL; + return chunk; +} + +static void +mp_free_big_chunk(struct mempool *pool, struct mempool_chunk *chunk) +{ + pool->total_size -= chunk->size + MP_CHUNK_TAIL; + free((void *)chunk - chunk->size); +} + +static void * +mp_new_chunk(struct mempool *pool, size_t size) +{ +#ifdef CONFIG_UCW_POOL_IS_MMAP + struct mempool_chunk *chunk; + chunk = page_alloc(size + MP_CHUNK_TAIL) + size; + chunk->size = size; + if (pool) + pool->total_size += size + MP_CHUNK_TAIL; + return chunk; +#else + return mp_new_big_chunk(pool, size); +#endif +} + +static void +mp_free_chunk(struct mempool *pool, struct mempool_chunk *chunk) +{ +#ifdef CONFIG_UCW_POOL_IS_MMAP + pool->total_size -= chunk->size + MP_CHUNK_TAIL; + page_free((void *)chunk - chunk->size, chunk->size + MP_CHUNK_TAIL); +#else + mp_free_big_chunk(pool, chunk); +#endif +} + +struct mempool * +mp_new(size_t chunk_size) +{ + chunk_size = mp_align_size(MAX(sizeof(struct mempool), chunk_size)); + struct mempool_chunk *chunk = mp_new_chunk(NULL, chunk_size); + struct mempool *pool = (void *)chunk - chunk_size; + DBG("Creating mempool %p with %u bytes long chunks", pool, chunk_size); + chunk->next = NULL; +#ifdef CONFIG_DEBUG + chunk->pool = pool; +#endif + *pool = (struct mempool) { + .allocator = { + .alloc = mp_allocator_alloc, + .realloc = mp_allocator_realloc, + .free = mp_allocator_free, + }, + .state = { .free = { chunk_size - sizeof(*pool) }, .last = { chunk } }, + .chunk_size = chunk_size, + .threshold = chunk_size >> 1, + .last_big = &pool->last_big, + .total_size = chunk->size + MP_CHUNK_TAIL, + }; + return pool; +} + +static void +mp_free_chain(struct mempool *pool, struct mempool_chunk *chunk) +{ + while (chunk) + { + struct mempool_chunk *next = chunk->next; + mp_free_chunk(pool, chunk); + chunk = next; + } +} + +static void +mp_free_big_chain(struct mempool *pool, struct mempool_chunk *chunk) +{ + while (chunk) + { + struct mempool_chunk *next = chunk->next; + mp_free_big_chunk(pool, chunk); + chunk = next; + } +} + +void +mp_delete(struct mempool *pool) +{ + DBG("Deleting mempool %p", pool); + mp_free_big_chain(pool, pool->state.last[1]); + mp_free_chain(pool, pool->unused); + mp_free_chain(pool, pool->state.last[0]); // can contain the mempool structure +} + +void +mp_flush(struct mempool *pool) +{ + mp_free_big_chain(pool, pool->state.last[1]); + struct mempool_chunk *chunk, *next; + for (chunk = pool->state.last[0]; chunk && (void *)chunk - chunk->size != pool; chunk = next) + { + next = chunk->next; + chunk->next = pool->unused; + pool->unused = chunk; + } + pool->state.last[0] = chunk; + pool->state.free[0] = chunk ? chunk->size - sizeof(*pool) : 0; + pool->state.last[1] = NULL; + pool->state.free[1] = 0; + pool->state.next = NULL; + pool->last_big = &pool->last_big; +} + +static void +mp_stats_chain(struct mempool *pool, struct mempool_chunk *chunk, struct mempool_stats *stats, uint idx) +{ + while (chunk) + { + stats->chain_size[idx] += chunk->size + MP_CHUNK_TAIL; + stats->chain_count[idx]++; + if (idx < 2) + { + stats->used_size += chunk->size; + if ((byte *)pool == (byte *)chunk - chunk->size) + stats->used_size -= sizeof(*pool); + } + chunk = chunk->next; + } + stats->total_size += stats->chain_size[idx]; +} + +void +mp_stats(struct mempool *pool, struct mempool_stats *stats) +{ + bzero(stats, sizeof(*stats)); + mp_stats_chain(pool, pool->state.last[0], stats, 0); + mp_stats_chain(pool, pool->state.last[1], stats, 1); + mp_stats_chain(pool, pool->unused, stats, 2); + stats->used_size -= pool->state.free[0] + pool->state.free[1]; + ASSERT(stats->total_size == pool->total_size); + ASSERT(stats->used_size <= stats->total_size); +} + +u64 +mp_total_size(struct mempool *pool) +{ + return pool->total_size; +} + +void +mp_shrink(struct mempool *pool, u64 min_total_size) +{ + while (1) + { + struct mempool_chunk *chunk = pool->unused; + if (!chunk || pool->total_size - (chunk->size + MP_CHUNK_TAIL) < min_total_size) + break; + pool->unused = chunk->next; + mp_free_chunk(pool, chunk); + } +} + +void * +mp_alloc_internal(struct mempool *pool, size_t size) +{ + struct mempool_chunk *chunk; + if (size <= pool->threshold) + { + pool->idx = 0; + if (pool->unused) + { + chunk = pool->unused; + pool->unused = chunk->next; + } + else + { + chunk = mp_new_chunk(pool, pool->chunk_size); +#ifdef CONFIG_DEBUG + chunk->pool = pool; +#endif + } + chunk->next = pool->state.last[0]; + pool->state.last[0] = chunk; + pool->state.free[0] = pool->chunk_size - size; + return (void *)chunk - pool->chunk_size; + } + else if (likely(size <= MP_SIZE_MAX)) + { + pool->idx = 1; + size_t aligned = ALIGN_TO(size, CPU_STRUCT_ALIGN); + chunk = mp_new_big_chunk(pool, aligned); + chunk->next = pool->state.last[1]; +#ifdef CONFIG_DEBUG + chunk->pool = pool; +#endif + pool->state.last[1] = chunk; + pool->state.free[1] = aligned - size; + return pool->last_big = (void *)chunk - aligned; + } + else + return NULL; +} + +void * +mp_alloc(struct mempool *pool, size_t size) +{ + return mp_alloc_fast(pool, size); +} + +void * +mp_alloc_noalign(struct mempool *pool, size_t size) +{ + return mp_alloc_fast_noalign(pool, size); +} + +void * +mp_alloc_zero(struct mempool *pool, size_t size) +{ + void *ptr = mp_alloc_fast(pool, size); + bzero(ptr, size); + return ptr; +} + +void * +mp_start_internal(struct mempool *pool, size_t size) +{ + void *ptr = mp_alloc_internal(pool, size); + if (!ptr) + return NULL; + pool->state.free[pool->idx] += size; + return ptr; +} + +void * +mp_start(struct mempool *pool, size_t size) +{ + return mp_start_fast(pool, size); +} + +void * +mp_start_noalign(struct mempool *pool, size_t size) +{ + return mp_start_fast_noalign(pool, size); +} + +void * +mp_grow_internal(struct mempool *pool, size_t size) +{ + if (unlikely(size > MP_SIZE_MAX)) + return NULL; + size_t avail = mp_avail(pool); + void *ptr = mp_ptr(pool); + if (pool->idx) + { + size_t amortized = likely(avail <= MP_SIZE_MAX / 2) ? avail * 2 : MP_SIZE_MAX; + amortized = MAX(amortized, size); + amortized = ALIGN_TO(amortized, CPU_STRUCT_ALIGN); + struct mempool_chunk *chunk = pool->state.last[1], *next = chunk->next; + pool->total_size = pool->total_size - chunk->size + amortized; + void *nptr = realloc(ptr, amortized + MP_CHUNK_TAIL); + if (!nptr) + return NULL; + ptr = nptr; + chunk = ptr + amortized; + chunk->next = next; + chunk->size = amortized; + pool->state.last[1] = chunk; + pool->state.free[1] = amortized; + pool->last_big = ptr; + return ptr; + } + else + { + void *p = mp_start_internal(pool, size); + memcpy(p, ptr, avail); + return p; + } +} + +size_t +mp_open(struct mempool *pool, void *ptr) +{ + return mp_open_fast(pool, ptr); +} + +void * +mp_realloc(struct mempool *pool, void *ptr, size_t size) +{ + return mp_realloc_fast(pool, ptr, size); +} + +void * +mp_realloc_zero(struct mempool *pool, void *ptr, size_t size) +{ + size_t old_size = mp_open_fast(pool, ptr); + ptr = mp_grow(pool, size); + if (size > old_size) + bzero(ptr + old_size, size - old_size); + mp_end(pool, ptr + size); + return ptr; +} + +void * +mp_spread_internal(struct mempool *pool, void *p, size_t size) +{ + void *old = mp_ptr(pool); + void *new = mp_grow_internal(pool, p-old+size); + if (!new) { + return NULL; + } + return p-old+new; +} + +void +mp_restore(struct mempool *pool, struct mempool_state *state) +{ + struct mempool_chunk *chunk, *next; + struct mempool_state s = *state; + for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next) + { + next = chunk->next; + chunk->next = pool->unused; + pool->unused = chunk; + } + for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next) + { + next = chunk->next; + mp_free_big_chunk(pool, chunk); + } + pool->state = s; + pool->last_big = &pool->last_big; +} + +struct mempool_state * +mp_push(struct mempool *pool) +{ + struct mempool_state state = pool->state; + struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p)); + *p = state; + pool->state.next = p; + return p; +} + +void +mp_pop(struct mempool *pool) +{ + ASSERT(pool->state.next); + mp_restore(pool, pool->state.next); +} + +#ifdef TEST + +#include <ucw/getopt.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +static void +fill(byte *ptr, uint len, uint magic) +{ + while (len--) + *ptr++ = (magic++ & 255); +} + +static void +check(byte *ptr, uint len, uint magic, uint align) +{ + ASSERT(!((uintptr_t)ptr & (align - 1))); + while (len--) + if (*ptr++ != (magic++ & 255)) + ASSERT(0); +} + +int main(int argc, char **argv) +{ + srand(time(NULL)); + log_init(argv[0]); + cf_def_file = NULL; + if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind) + die("Invalid usage"); + + uint max = 1000, n = 0, m = 0, can_realloc = 0; + void *ptr[max]; + struct mempool_state *state[max]; + uint len[max], num[max], align[max]; + struct mempool *mp = mp_new(128), mp_static; + + for (uint i = 0; i < 5000; i++) + { + for (uint j = 0; j < n; j++) + check(ptr[j], len[j], j, align[j]); +#if 0 + DBG("free_small=%u free_big=%u idx=%u chunk_size=%u last_big=%p", mp->state.free[0], mp->state.free[1], mp->idx, mp->chunk_size, mp->last_big); + for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next) + DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size); + for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next) + DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size); +#endif + int r = random_max(100); + if ((r -= 1) < 0) + { + DBG("flush"); + mp_flush(mp); + n = m = 0; + } + else if ((r -= 1) < 0) + { + DBG("delete & new"); + mp_delete(mp); + if (random_max(2)) + mp = mp_new(random_max(0x1000) + 1); + else + mp = &mp_static, mp_init(mp, random_max(512) + 1); + n = m = 0; + } + else if (n < max && (r -= 30) < 0) + { + len[n] = random_max(0x2000); + DBG("alloc(%u)", len[n]); + align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1; + ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]); + DBG(" -> (%p)", ptr[n]); + fill(ptr[n], len[n], n); + n++; + can_realloc = 1; + } + else if (n < max && (r -= 20) < 0) + { + len[n] = random_max(0x2000); + DBG("start(%u)", len[n]); + align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1; + ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]); + DBG(" -> (%p)", ptr[n]); + fill(ptr[n], len[n], n); + n++; + can_realloc = 1; + goto grow; + } + else if (can_realloc && n && (r -= 10) < 0) + { + if (mp_open(mp, ptr[n - 1]) != len[n - 1]) + ASSERT(0); +grow: + { + uint k = n - 1; + for (uint i = random_max(4); i--; ) + { + uint l = len[k]; + len[k] = random_max(0x2000); + DBG("grow(%u)", len[k]); + ptr[k] = mp_grow(mp, len[k]); + DBG(" -> (%p)", ptr[k]); + check(ptr[k], MIN(l, len[k]), k, align[k]); + fill(ptr[k], len[k], k); + } + mp_end(mp, ptr[k] + len[k]); + } + } + else if (can_realloc && n && (r -= 20) < 0) + { + uint i = n - 1, l = len[i]; + DBG("realloc(%p, %u)", ptr[i], len[i]); + ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000)); + DBG(" -> (%p, %u)", ptr[i], len[i]); + check(ptr[i], MIN(len[i], l), i, align[i]); + fill(ptr[i], len[i], i); + } + else if (m < max && (r -= 5) < 0) + { + DBG("push(%u)", m); + num[m] = n; + state[m++] = mp_push(mp); + can_realloc = 0; + } + else if (m && (r -= 2) < 0) + { + m--; + DBG("pop(%u)", m); + mp_pop(mp); + n = num[m]; + can_realloc = 0; + } + else if (m && (r -= 1) < 0) + { + uint i = random_max(m); + DBG("restore(%u)", i); + mp_restore(mp, state[i]); + n = num[m = i]; + can_realloc = 0; + } + else if (can_realloc && n && (r -= 5) < 0) + ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]); + else + { + struct mempool_stats stats; + mp_stats(mp, &stats); + } + } + + mp_delete(mp); + return 0; +} + +#endif diff --git a/contrib/ucw/mempool.h b/contrib/ucw/mempool.h new file mode 100644 index 0000000..d9092a7 --- /dev/null +++ b/contrib/ucw/mempool.h @@ -0,0 +1,572 @@ +/* + * UCW Library -- Memory Pools + * + * (c) 1997--2015 Martin Mares <mj@ucw.cz> + * (c) 2007 Pavel Charvat <pchar@ucw.cz> + * SPDX-License-Identifier: LGPL-2.1-or-later + * Source: https://www.ucw.cz/libucw/ + */ + +#ifndef _UCW_POOLS_H +#define _UCW_POOLS_H + +#include "lib/defines.h" +#include <ucw/alloc.h> +#include <ucw/config.h> +#include <ucw/lib.h> +#include <string.h> + +#ifdef CONFIG_UCW_CLEAN_ABI +#define mp_alloc ucw_mp_alloc +#define mp_alloc_internal ucw_mp_alloc_internal +#define mp_alloc_noalign ucw_mp_alloc_noalign +#define mp_alloc_zero ucw_mp_alloc_zero +#define mp_delete ucw_mp_delete +#define mp_flush ucw_mp_flush +#define mp_grow_internal ucw_mp_grow_internal +#define mp_init ucw_mp_init +#define mp_memdup ucw_mp_memdup +#define mp_multicat ucw_mp_multicat +#define mp_new ucw_mp_new +#define mp_open ucw_mp_open +#define mp_pop ucw_mp_pop +#define mp_printf ucw_mp_printf +#define mp_printf_append ucw_mp_printf_append +#define mp_push ucw_mp_push +#define mp_realloc ucw_mp_realloc +#define mp_realloc_zero ucw_mp_realloc_zero +#define mp_restore ucw_mp_restore +#define mp_shrink ucw_mp_shrink +#define mp_spread_internal ucw_mp_spread_internal +#define mp_start ucw_mp_start +#define mp_start_internal ucw_mp_start_internal +#define mp_start_noalign ucw_mp_start_noalign +#define mp_stats ucw_mp_stats +#define mp_str_from_mem ucw_mp_str_from_mem +#define mp_strdup ucw_mp_strdup +#define mp_strjoin ucw_mp_strjoin +#define mp_total_size ucw_mp_total_size +#define mp_vprintf ucw_mp_vprintf +#define mp_vprintf_append ucw_mp_vprintf_append +#endif + +/*** + * [[defs]] + * Definitions + * ----------- + ***/ + +/** + * Memory pool state (see @mp_push(), ...). + * You should use this one as an opaque handle only, the insides are internal. + **/ +struct mempool_state { + size_t free[2]; + void *last[2]; + struct mempool_state *next; +}; + +/** + * Memory pool. + * You should use this one as an opaque handle only, the insides are internal. + **/ +struct mempool { + struct ucw_allocator allocator; // This must be the first element + struct mempool_state state; + void *unused, *last_big; + size_t chunk_size, threshold; + uint idx; + u64 total_size; +}; + +struct mempool_stats { /** Mempool statistics. See @mp_stats(). **/ + u64 total_size; /* Real allocated size in bytes */ + u64 used_size; /* Estimated size allocated from mempool to application */ + uint chain_count[3]; /* Number of allocated chunks in small/big/unused chains */ + u64 chain_size[3]; /* Size of allocated chunks in small/big/unused chains */ +}; + +/*** + * [[basic]] + * Basic manipulation + * ------------------ + ***/ + +/** + * Initialize a given mempool structure. + * @chunk_size must be in the interval `[1, SIZE_MAX / 2]`. + * It will allocate memory by this large chunks and take + * memory to satisfy requests from them. + * + * Memory pools can be treated as <<trans:respools,resources>>, see <<trans:res_mempool()>>. + **/ +KR_EXPORT +void mp_init(struct mempool *pool, size_t chunk_size); + +/** + * Allocate and initialize a new memory pool. + * See @mp_init() for @chunk_size limitations. + * + * The new mempool structure is allocated on the new mempool. + * + * Memory pools can be treated as <<trans:respools,resources>>, see <<trans:res_mempool()>>. + **/ +KR_EXPORT +struct mempool *mp_new(size_t chunk_size); + +/** + * Cleanup mempool initialized by mp_init or mp_new. + * Frees all the memory allocated by this mempool and, + * if created by @mp_new(), the @pool itself. + **/ +KR_EXPORT +void mp_delete(struct mempool *pool); + +/** + * Frees all data on a memory pool, but leaves it working. + * It can keep some of the chunks allocated to serve + * further allocation requests. Leaves the @pool alive, + * even if it was created with @mp_new(). + **/ +KR_EXPORT +void mp_flush(struct mempool *pool); + +/** + * Compute some statistics for debug purposes. + * See the definition of the <<struct_mempool_stats,mempool_stats structure>>. + * This function scans the chunk list, so it can be slow. If you are interested + * in total memory consumption only, mp_total_size() is faster. + **/ +void mp_stats(struct mempool *pool, struct mempool_stats *stats); + +/** + * Return how many bytes were allocated by the pool, including unused parts + * of chunks. This function runs in constant time. + **/ +u64 mp_total_size(struct mempool *pool); + +/** + * Release unused chunks of memory reserved for further allocation + * requests, but stop if mp_total_size() would drop below @min_total_size. + **/ +void mp_shrink(struct mempool *pool, u64 min_total_size); + +/*** + * [[alloc]] + * Allocation routines + * ------------------- + ***/ + +/* For internal use only, do not call directly */ +void *mp_alloc_internal(struct mempool *pool, size_t size) LIKE_MALLOC; + +/** + * The function allocates new @size bytes on a given memory pool. + * If the @size is zero, the resulting pointer is undefined, + * but it may be safely reallocated or used as the parameter + * to other functions below. + * + * The resulting pointer is always aligned to a multiple of + * `CPU_STRUCT_ALIGN` bytes and this condition remains true also + * after future reallocations. + **/ +KR_EXPORT +void *mp_alloc(struct mempool *pool, size_t size); + +/** + * The same as @mp_alloc(), but the result may be unaligned. + **/ +void *mp_alloc_noalign(struct mempool *pool, size_t size); + +/** + * The same as @mp_alloc(), but fills the newly allocated memory with zeroes. + **/ +void *mp_alloc_zero(struct mempool *pool, size_t size); + +/** + * Inlined version of @mp_alloc(). + **/ +static inline void *mp_alloc_fast(struct mempool *pool, size_t size) +{ + size_t avail = pool->state.free[0] & ~(size_t)(CPU_STRUCT_ALIGN - 1); + if (size <= avail) + { + pool->state.free[0] = avail - size; + return (byte *)pool->state.last[0] - avail; + } + else + return mp_alloc_internal(pool, size); +} + +/** + * Inlined version of @mp_alloc_noalign(). + **/ +static inline void *mp_alloc_fast_noalign(struct mempool *pool, size_t size) +{ + if (size <= pool->state.free[0]) + { + void *ptr = (byte *)pool->state.last[0] - pool->state.free[0]; + pool->state.free[0] -= size; + return ptr; + } + else + return mp_alloc_internal(pool, size); +} + +/** + * Return a generic allocator representing the given mempool. + **/ +static inline struct ucw_allocator *mp_get_allocator(struct mempool *mp) +{ + return &mp->allocator; +} + +/*** + * [[gbuf]] + * Growing buffers + * --------------- + * + * You do not need to know, how a buffer will need to be large, + * you can grow it incrementally to needed size. You can grow only + * one buffer at a time on a given mempool. + * + * Similar functionality is provided by <<growbuf:,growing buffes>> module. + ***/ + +/* For internal use only, do not call directly */ +void *mp_start_internal(struct mempool *pool, size_t size) LIKE_MALLOC; +void *mp_grow_internal(struct mempool *pool, size_t size); +void *mp_spread_internal(struct mempool *pool, void *p, size_t size); + +static inline uint mp_idx(struct mempool *pool, void *ptr) +{ + return ptr == pool->last_big; +} + +/** + * Open a new growing buffer (at least @size bytes long). + * If the @size is zero, the resulting pointer is undefined, + * but it may be safely reallocated or used as the parameter + * to other functions below. + * + * The resulting pointer is always aligned to a multiple of + * `CPU_STRUCT_ALIGN` bytes and this condition remains true also + * after future reallocations. There is an unaligned version as well. + * + * Keep in mind that you can't make any other pool allocations + * before you "close" the growing buffer with @mp_end(). + */ +void *mp_start(struct mempool *pool, size_t size); +void *mp_start_noalign(struct mempool *pool, size_t size); + +/** + * Inlined version of @mp_start(). + **/ +static inline void *mp_start_fast(struct mempool *pool, size_t size) +{ + size_t avail = pool->state.free[0] & ~(size_t)(CPU_STRUCT_ALIGN - 1); + if (size <= avail) + { + pool->idx = 0; + pool->state.free[0] = avail; + return (byte *)pool->state.last[0] - avail; + } + else + return mp_start_internal(pool, size); +} + +/** + * Inlined version of @mp_start_noalign(). + **/ +static inline void *mp_start_fast_noalign(struct mempool *pool, size_t size) +{ + if (size <= pool->state.free[0]) + { + pool->idx = 0; + return (byte *)pool->state.last[0] - pool->state.free[0]; + } + else + return mp_start_internal(pool, size); +} + +/** + * Return start pointer of the growing buffer allocated by latest @mp_start() or a similar function. + **/ +static inline void *mp_ptr(struct mempool *pool) +{ + return (byte *)pool->state.last[pool->idx] - pool->state.free[pool->idx]; +} + +/** + * Return the number of bytes available for extending the growing buffer. + * (Before a reallocation will be needed). + **/ +static inline size_t mp_avail(struct mempool *pool) +{ + return pool->state.free[pool->idx]; +} + +/** + * Grow the buffer allocated by @mp_start() to be at least @size bytes long + * (@size may be less than @mp_avail(), even zero). Reallocated buffer may + * change its starting position. The content will be unchanged to the minimum + * of the old and new sizes; newly allocated memory will be uninitialized. + * Multiple calls to mp_grow() have amortized linear cost wrt. the maximum value of @size. */ +static inline void *mp_grow(struct mempool *pool, size_t size) +{ + return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size); +} + +/** + * Grow the buffer by at least one byte -- equivalent to <<mp_grow(),`mp_grow`>>`(@pool, @mp_avail(pool) + 1)`. + **/ +static inline void *mp_expand(struct mempool *pool) +{ + return mp_grow_internal(pool, mp_avail(pool) + 1); +} + +/** + * Ensure that there is at least @size bytes free after @p, + * if not, reallocate and adjust @p. + **/ +static inline void *mp_spread(struct mempool *pool, void *p, size_t size) +{ + return (((size_t)((byte *)pool->state.last[pool->idx] - (byte *)p) >= size) ? p : mp_spread_internal(pool, p, size)); +} + +/** + * Append a character to the growing buffer. Called with @p pointing after + * the last byte in the buffer, returns a pointer after the last byte + * of the new (possibly reallocated) buffer. + **/ +static inline char *mp_append_char(struct mempool *pool, char *p, uint c) +{ + p = mp_spread(pool, p, 1); + *p++ = c; + return p; +} + +/** + * Append a memory block to the growing buffer. Called with @p pointing after + * the last byte in the buffer, returns a pointer after the last byte + * of the new (possibly reallocated) buffer. + **/ +static inline void *mp_append_block(struct mempool *pool, void *p, const void *block, size_t size) +{ + char *q = mp_spread(pool, p, size); + memcpy(q, block, size); + return q + size; +} + +/** + * Append a string to the growing buffer. Called with @p pointing after + * the last byte in the buffer, returns a pointer after the last byte + * of the new (possibly reallocated) buffer. + **/ +static inline void *mp_append_string(struct mempool *pool, void *p, const char *str) +{ + return mp_append_block(pool, p, str, strlen(str)); +} + +/** + * Close the growing buffer. The @end must point just behind the data, you want to keep + * allocated (so it can be in the interval `[@mp_ptr(@pool), @mp_ptr(@pool) + @mp_avail(@pool)]`). + * Returns a pointer to the beginning of the just closed block. + **/ +static inline void *mp_end(struct mempool *pool, void *end) +{ + void *p = mp_ptr(pool); + pool->state.free[pool->idx] = (byte *)pool->state.last[pool->idx] - (byte *)end; + return p; +} + +/** + * Close the growing buffer as a string. That is, append a zero byte and call mp_end(). + **/ +static inline char *mp_end_string(struct mempool *pool, void *end) +{ + end = mp_append_char(pool, end, 0); + return mp_end(pool, end); +} + +/** + * Return size in bytes of the last allocated memory block (with @mp_alloc() or @mp_end()). + **/ +static inline size_t mp_size(struct mempool *pool, void *ptr) +{ + uint idx = mp_idx(pool, ptr); + return ((byte *)pool->state.last[idx] - (byte *)ptr) - pool->state.free[idx]; +} + +/** + * Open the last memory block (allocated with @mp_alloc() or @mp_end()) + * for growing and return its size in bytes. The contents and the start pointer + * remain unchanged. Do not forget to call @mp_end() to close it. + **/ +size_t mp_open(struct mempool *pool, void *ptr); + +/** + * Inlined version of @mp_open(). + **/ +static inline size_t mp_open_fast(struct mempool *pool, void *ptr) +{ + pool->idx = mp_idx(pool, ptr); + size_t size = ((byte *)pool->state.last[pool->idx] - (byte *)ptr) - pool->state.free[pool->idx]; + pool->state.free[pool->idx] += size; + return size; +} + +/** + * Reallocate the last memory block (allocated with @mp_alloc() or @mp_end()) + * to the new @size. Behavior is similar to @mp_grow(), but the resulting + * block is closed. + **/ +void *mp_realloc(struct mempool *pool, void *ptr, size_t size); + +/** + * The same as @mp_realloc(), but fills the additional bytes (if any) with zeroes. + **/ +void *mp_realloc_zero(struct mempool *pool, void *ptr, size_t size); + +/** + * Inlined version of @mp_realloc(). + **/ +static inline void *mp_realloc_fast(struct mempool *pool, void *ptr, size_t size) +{ + mp_open_fast(pool, ptr); + ptr = mp_grow(pool, size); + mp_end(pool, (byte *)ptr + size); + return ptr; +} + +/*** + * [[store]] + * Storing and restoring state + * --------------------------- + * + * Mempools can remember history of what was allocated and return back + * in time. + ***/ + +/** + * Save the current state of a memory pool. + * Do not call this function with an opened growing buffer. + **/ +static inline void mp_save(struct mempool *pool, struct mempool_state *state) +{ + *state = pool->state; + pool->state.next = state; +} + +/** + * Save the current state to a newly allocated mempool_state structure. + * Do not call this function with an opened growing buffer. + **/ +struct mempool_state *mp_push(struct mempool *pool); + +/** + * Restore the state saved by @mp_save() or @mp_push() and free all + * data allocated after that point (including the state structure itself). + * You can't reallocate the last memory block from the saved state. + **/ +void mp_restore(struct mempool *pool, struct mempool_state *state); + +/** + * Inlined version of @mp_restore(). + **/ +static inline void mp_restore_fast(struct mempool *pool, struct mempool_state *state) +{ + if (pool->state.last[0] != state->last[0] || pool->state.last[1] != state->last[1]) + mp_restore(pool, state); + else + { + pool->state = *state; + pool->last_big = &pool->last_big; + } +} + +/** + * Restore the state saved by the last call to @mp_push(). + * @mp_pop() and @mp_push() works as a stack so you can push more states safely. + **/ +void mp_pop(struct mempool *pool); + + +/*** + * [[string]] + * String operations + * ----------------- + ***/ + +char *mp_strdup(struct mempool *, const char *) LIKE_MALLOC; /** Makes a copy of a string on a mempool. Returns NULL for NULL string. **/ +void *mp_memdup(struct mempool *, const void *, size_t) LIKE_MALLOC; /** Makes a copy of a memory block on a mempool. **/ +/** + * Concatenates all passed strings. The last parameter must be NULL. + * This will concatenate two strings: + * + * char *message = mp_multicat(pool, "hello ", "world", NULL); + **/ +char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK; +/** + * Concatenates two strings and stores result on @mp. + */ +static inline char *LIKE_MALLOC mp_strcat(struct mempool *mp, const char *x, const char *y) +{ + return mp_multicat(mp, x, y, NULL); +} +/** + * Join strings and place @sep between each two neighboring. + * @p is the mempool to provide memory, @a is array of strings and @n + * tells how many there is of them. + **/ +char *mp_strjoin(struct mempool *p, char **a, uint n, uint sep) LIKE_MALLOC; +/** + * Convert memory block to a string. Makes a copy of the given memory block + * in the mempool @p, adding an extra terminating zero byte at the end. + **/ +char *mp_str_from_mem(struct mempool *p, const void *mem, size_t len) LIKE_MALLOC; + + +/*** + * [[format]] + * Formatted output + * --------------- + ***/ + +/** + * printf() into a in-memory string, allocated on the memory pool. + **/ +KR_EXPORT +char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC; +/** + * Like @mp_printf(), but uses `va_list` for parameters. + **/ +char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC; +/** + * Like @mp_printf(), but it appends the data at the end of string + * pointed to by @ptr. The string is @mp_open()ed, so you have to + * provide something that can be. + * + * Returns pointer to the beginning of the string (the pointer may have + * changed due to reallocation). + * + * In some versions of LibUCW, this function was called mp_append_printf(). However, + * this name turned out to be confusing -- unlike other appending functions, this one is + * not called on an opened growing buffer. The old name will be preserved for backward + * compatibility for the time being. + **/ +KR_EXPORT +char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4); +#define mp_append_printf mp_printf_append +/** + * Like @mp_printf_append(), but uses `va_list` for parameters. + * + * In some versions of LibUCW, this function was called mp_append_vprintf(). However, + * this name turned out to be confusing -- unlike other appending functions, this one is + * not called on an opened growing buffer. The old name will be preserved for backward + * compatibility for the time being. + **/ +char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args); +#define mp_append_vprintf mp_vprintf_append + +#endif diff --git a/contrib/wire.h b/contrib/wire.h new file mode 100644 index 0000000..bec6db5 --- /dev/null +++ b/contrib/wire.h @@ -0,0 +1,163 @@ +/* Copyright (C) 2011-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ +/*! + * \file + * + * \brief Wire integer operations. + * + * \addtogroup contrib + * @{ + */ + +#pragma once + +#include <stdint.h> +#include <string.h> + +#if defined(__linux__) || defined(__gnu_hurd__) || \ + (defined(__FreeBSD_kernel__) && defined(__GLIBC__)) +# include <endian.h> +# ifndef be64toh +# include <arpa/inet.h> +# include <byteswap.h> +# if BYTE_ORDER == LITTLE_ENDIAN +# define be16toh(x) ntohs(x) +# define be32toh(x) ntohl(x) +# define be64toh(x) bswap_64 (x) +# define le16toh(x) (x) +# define le32toh(x) (x) +# define le64toh(x) (x) +# else +# define be16toh(x) (x) +# define be32toh(x) (x) +# define be64toh(x) (x) +# define le16toh(x) ntohs(x) +# define le32toh(x) ntohl(x) +# define le64toh(x) bswap_64 (x) +# endif +# endif +#elif defined(__FreeBSD__) || defined(__NetBSD__) +# include <sys/endian.h> +#elif defined(__OpenBSD__) +# include <endian.h> +#elif defined(__APPLE__) +# include <libkern/OSByteOrder.h> +# define be16toh(x) OSSwapBigToHostInt16(x) +# define be32toh(x) OSSwapBigToHostInt32(x) +# define be64toh(x) OSSwapBigToHostInt64(x) +# define htobe16(x) OSSwapHostToBigInt16(x) +# define htobe32(x) OSSwapHostToBigInt32(x) +# define htobe64(x) OSSwapHostToBigInt64(x) +# define le16toh(x) OSSwapLittleToHostInt16(x) +# define le32toh(x) OSSwapLittleToHostInt32(x) +# define le64toh(x) OSSwapLittleToHostInt64(x) +# define htole16(x) OSSwapHostToLittleInt16(x) +# define htole32(x) OSSwapHostToLittleInt32(x) +# define htole64(x) OSSwapHostToLittleInt64(x) +#endif + +/*! + * \brief Reads 2 bytes from the wireformat data. + * + * \param pos Data to read the 2 bytes from. + * + * \return The 2 bytes read, in host byte order. + */ +inline static uint16_t wire_read_u16(const uint8_t *pos) +{ + return be16toh(*(uint16_t *)pos); +} + +/*! + * \brief Reads 4 bytes from the wireformat data. + * + * \param pos Data to read the 4 bytes from. + * + * \return The 4 bytes read, in host byte order. + */ +inline static uint32_t wire_read_u32(const uint8_t *pos) +{ + return be32toh(*(uint32_t *)pos); +} + +/*! + * \brief Reads 6 bytes from the wireformat data. + * + * \param pos Data to read the 6 bytes from. + * + * \return The 6 bytes read, in host byte order. + */ +inline static uint64_t wire_read_u48(const uint8_t *pos) +{ + uint64_t input = 0; + memcpy((uint8_t *)&input + 1, pos, 6); + return be64toh(input) >> 8; +} + +/*! + * \brief Read 8 bytes from the wireformat data. + * + * \param pos Data to read the 8 bytes from. + * + * \return The 8 bytes read, in host byte order. + */ +inline static uint64_t wire_read_u64(const uint8_t *pos) +{ + return be64toh(*(uint64_t *)pos); +} + +/*! + * \brief Writes 2 bytes in wireformat. + * + * The data are stored in network byte order (big endian). + * + * \param pos Position where to put the 2 bytes. + * \param data Data to put. + */ +inline static void wire_write_u16(uint8_t *pos, uint16_t data) +{ + *(uint16_t *)pos = htobe16(data); +} + +/*! + * \brief Writes 4 bytes in wireformat. + * + * The data are stored in network byte order (big endian). + * + * \param pos Position where to put the 4 bytes. + * \param data Data to put. + */ +inline static void wire_write_u32(uint8_t *pos, uint32_t data) +{ + *(uint32_t *)pos = htobe32(data); +} + +/*! + * \brief Writes 6 bytes in wireformat. + * + * The data are stored in network byte order (big endian). + * + * \param pos Position where to put the 4 bytes. + * \param data Data to put. + */ +inline static void wire_write_u48(uint8_t *pos, uint64_t data) +{ + uint64_t swapped = htobe64(data << 8); + memcpy(pos, (uint8_t *)&swapped + 1, 6); +} + +/*! + * \brief Writes 8 bytes in wireformat. + * + * The data are stored in network byte order (big endian). + * + * \param pos Position where to put the 8 bytes. + * \param data Data to put. + */ +inline static void wire_write_u64(uint8_t *pos, uint64_t data) +{ + *(uint64_t *)pos = htobe64(data); +} + +/*! @} */ diff --git a/contrib/wire.spdx b/contrib/wire.spdx new file mode 100644 index 0000000..1054c55 --- /dev/null +++ b/contrib/wire.spdx @@ -0,0 +1,10 @@ +SPDXVersion: SPDX-2.1 +DataLicense: CC0-1.0 +SPDXID: SPDXRef-DOCUMENT +DocumentName: knotdns-wire +DocumentNamespace: http://spdx.org/spdxdocs/spdx-v2.1-0f7c0ad6-ea88-44b4-a93a-850f3b6ccade + +PackageName: knotdns-wire +PackageDownloadLocation: git+https://gitlab.nic.cz/knot/knot-dns.git@824ce5e81bc1a1d333de3042b2745bb2387dc2ff#src/contrib/wire.h +PackageOriginator: Organization: Knot DNS contributors +PackageLicenseDeclared: GPL-3.0-or-later |