Home | History | Annotate | Line # | Download | only in isc 
      1 /*	$NetBSD: ascii.h,v 1.2 2025/01/26 16:25:40 christos Exp $	*/
      2 
      3 /*
      4  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
      5  *
      6  * SPDX-License-Identifier: MPL-2.0
      7  *
      8  * This Source Code Form is subject to the terms of the Mozilla Public
      9  * License, v. 2.0. If a copy of the MPL was not distributed with this
     10  * file, you can obtain one at https://mozilla.org/MPL/2.0/.
     11  *
     12  * See the COPYRIGHT file distributed with this work for additional
     13  * information regarding copyright ownership.
     14  */
     15 
     16 #pragma once
     17 
     18 #include <stdbool.h>
     19 #include <stdint.h>
     20 #include <string.h>
     21 
     22 #include <isc/endian.h>
     23 
     24 /*
     25  * ASCII case conversion
     26  */
     27 extern const uint8_t isc__ascii_tolower[256];
     28 extern const uint8_t isc__ascii_toupper[256];
     29 
     30 /*
     31  * Wrappers so we don't have to cast all over the place like <ctype.h>
     32  */
     33 #define isc_ascii_tolower(c) isc__ascii_tolower[(uint8_t)(c)]
     34 #define isc_ascii_toupper(c) isc__ascii_toupper[(uint8_t)(c)]
     35 
     36 /*
     37  * A variant tolower() implementation with no memory accesses,
     38  * for use when the compiler is able to autovectorize.
     39  */
     40 static inline uint8_t
     41 isc__ascii_tolower1(uint8_t c) {
     42 	return c + ('a' - 'A') * ('A' <= c && c <= 'Z');
     43 }
     44 
     45 /*
     46  * Copy `len` bytes from `src` to `dst`, converting to lower case.
     47  */
     48 static inline void
     49 isc_ascii_lowercopy(uint8_t *dst, const uint8_t *src, unsigned int len) {
     50 	while (len-- > 0) {
     51 		*dst++ = isc__ascii_tolower1(*src++);
     52 	}
     53 }
     54 
     55 /*
     56  * Convert a string to lower case in place
     57  */
     58 static inline void
     59 isc_ascii_strtolower(char *str) {
     60 	isc_ascii_lowercopy((uint8_t *)str, (uint8_t *)str,
     61 			    (unsigned int)strlen(str));
     62 }
     63 
     64 /*
     65  * Convert 8 bytes to lower case, using SWAR tricks (SIMD within a register).
     66  * Based on "Hacker's Delight" by Henry S. Warren, "searching for a value in a
     67  * given range", p. 95. Eight bytes is wider than many labels in DNS names, so
     68  * it does not seem worth dealing with the portability issues of wide vector
     69  * registers. If there was a vector string load instruction (analogous to
     70  * memove() below) the balance might be different.
     71  */
     72 static inline uint64_t
     73 isc_ascii_tolower8(uint64_t octets) {
     74 	/*
     75 	 * Multiply a single-byte constant by `all_bytes` to replicate
     76 	 * it to all eight bytes in a word.
     77 	 */
     78 	uint64_t all_bytes = 0x0101010101010101;
     79 	/*
     80 	 * Clear the top bit of each byte to make space for a per-byte flag.
     81 	 */
     82 	uint64_t heptets = octets & (0x7F * all_bytes);
     83 	/*
     84 	 * We will need to avoid going wrong if our flag bits were originally
     85 	 * set, and clear calculation leftovers in our non-flag bits
     86 	 */
     87 	uint64_t is_ascii = ~octets & (0x80 * all_bytes);
     88 	/*
     89 	 * To compare a heptet to `N`, we can add `0x7F - N` so that carry
     90 	 * propagation will set the flag when our heptet is greater than `N`
     91 	 */
     92 	uint64_t is_gt_Z = heptets + (0x7F - 'Z') * all_bytes;
     93 	/*
     94 	 * Add one for greater-than-or-equal comparison
     95 	 */
     96 	uint64_t is_ge_A = heptets + (0x80 - 'A') * all_bytes;
     97 	/*
     98 	 * Now we have what we need to identify the ascii uppercase bytes
     99 	 */
    100 	uint64_t is_upper = (is_ge_A ^ is_gt_Z) & is_ascii;
    101 	/*
    102 	 * Move the is_upper flag bits to bit 0x20 (which is 'a' - 'A')
    103 	 * and use them to adjust each byte as required
    104 	 */
    105 	return octets | (is_upper >> 2);
    106 }
    107 
    108 /*
    109  * Same, but 4 bytes at a time, used by isc_halfsiphash24()
    110  */
    111 static inline uint32_t
    112 isc_ascii_tolower4(uint32_t octets) {
    113 	uint32_t all_bytes = 0x01010101;
    114 	uint32_t heptets = octets & (0x7F * all_bytes);
    115 	uint32_t is_ascii = ~octets & (0x80 * all_bytes);
    116 	uint32_t is_gt_Z = heptets + (0x7F - 'Z') * all_bytes;
    117 	uint32_t is_ge_A = heptets + (0x80 - 'A') * all_bytes;
    118 	uint32_t is_upper = (is_ge_A ^ is_gt_Z) & is_ascii;
    119 	return octets | (is_upper >> 2);
    120 }
    121 
    122 /*
    123  * Helper function to do an unaligned load of 8 bytes in host byte order
    124  */
    125 static inline uint64_t
    126 isc__ascii_load8(const uint8_t *ptr) {
    127 	uint64_t bytes = 0;
    128 	memmove(&bytes, ptr, sizeof(bytes));
    129 	return bytes;
    130 }
    131 
    132 /*
    133  * Compare `len` bytes at `a` and `b` for case-insensitive equality
    134  */
    135 static inline bool
    136 isc_ascii_lowerequal(const uint8_t *a, const uint8_t *b, unsigned int len) {
    137 	uint64_t a8 = 0, b8 = 0;
    138 	while (len >= 8) {
    139 		a8 = isc_ascii_tolower8(isc__ascii_load8(a));
    140 		b8 = isc_ascii_tolower8(isc__ascii_load8(b));
    141 		if (a8 != b8) {
    142 			return false;
    143 		}
    144 		len -= 8;
    145 		a += 8;
    146 		b += 8;
    147 	}
    148 	while (len-- > 0) {
    149 		if (isc_ascii_tolower(*a++) != isc_ascii_tolower(*b++)) {
    150 			return false;
    151 		}
    152 	}
    153 	return true;
    154 }
    155 
    156 /*
    157  * Compare `len` bytes at `a` and `b` for case-insensitive order.
    158  * Unlike the previous functions (which do not need to care about byte
    159  * order) here we need to ensure the comparisons are lexicographic,
    160  * i.e. they treat the strings as big-endian numbers.
    161  */
    162 static inline int
    163 isc_ascii_lowercmp(const uint8_t *a, const uint8_t *b, unsigned int len) {
    164 	uint64_t a8 = 0, b8 = 0;
    165 	while (len >= 8) {
    166 		a8 = isc_ascii_tolower8(htobe64(isc__ascii_load8(a)));
    167 		b8 = isc_ascii_tolower8(htobe64(isc__ascii_load8(b)));
    168 		if (a8 != b8) {
    169 			goto ret;
    170 		}
    171 		len -= 8;
    172 		a += 8;
    173 		b += 8;
    174 	}
    175 	while (len-- > 0) {
    176 		a8 = isc_ascii_tolower(*a++);
    177 		b8 = isc_ascii_tolower(*b++);
    178 		if (a8 != b8) {
    179 			goto ret;
    180 		}
    181 	}
    182 ret:
    183 	if (a8 < b8) {
    184 		return -1;
    185 	}
    186 	if (a8 > b8) {
    187 		return +1;
    188 	}
    189 	return 0;
    190 }
    191