diff options
Diffstat (limited to 'src/lib/util')
-rw-r--r-- | src/lib/util/corefile.cpp | 22 | ||||
-rw-r--r-- | src/lib/util/corefile.h | 21 | ||||
-rw-r--r-- | src/lib/util/corestr.cpp | 95 | ||||
-rw-r--r-- | src/lib/util/corestr.h | 7 | ||||
-rw-r--r-- | src/lib/util/unicode.cpp | 170 | ||||
-rw-r--r-- | src/lib/util/unicode.h | 17 |
6 files changed, 235 insertions, 97 deletions
diff --git a/src/lib/util/corefile.cpp b/src/lib/util/corefile.cpp index 264d80f4113..78a484c5511 100644 --- a/src/lib/util/corefile.cpp +++ b/src/lib/util/corefile.cpp @@ -23,9 +23,10 @@ #include <ctype.h> - namespace util { + namespace { + /*************************************************************************** VALIDATION ***************************************************************************/ @@ -336,23 +337,6 @@ private: /*************************************************************************** - INLINE FUNCTIONS -***************************************************************************/ - -/*------------------------------------------------- - is_directory_separator - is a given character - a directory separator? The following logic - works for most platforms --------------------------------------------------*/ - -inline int is_directory_separator(char c) -{ - return (c == '\\' || c == '/' || c == ':'); -} - - - -/*************************************************************************** core_text_file ***************************************************************************/ @@ -1275,7 +1259,7 @@ core_file::core_file() std::string core_filename_extract_base(const std::string &name, bool strip_extension) { // find the start of the basename - auto const start = std::find_if(name.rbegin(), name.rend(), [](char c) { return util::is_directory_separator(c); }); + auto const start = std::find_if(name.rbegin(), name.rend(), &util::is_directory_separator); // find the end of the basename auto const chop_position = strip_extension diff --git a/src/lib/util/corefile.h b/src/lib/util/corefile.h index 2c4a5da8217..d286cb866ac 100644 --- a/src/lib/util/corefile.h +++ b/src/lib/util/corefile.h @@ -7,11 +7,11 @@ Core file I/O interface functions and definitions. ***************************************************************************/ +#ifndef MAME_LIB_UTIL_COREFILE_H +#define MAME_LIB_UTIL_COREFILE_H #pragma once -#ifndef MAME_LIB_UTIL_COREFILE_H -#define MAME_LIB_UTIL_COREFILE_H #include "corestr.h" #include "coretmpl.h" @@ -23,6 +23,7 @@ namespace util { + /*************************************************************************** ADDITIONAL OPEN FLAGS ***************************************************************************/ @@ -130,6 +131,22 @@ protected: core_file(); }; + +/*************************************************************************** + INLINE FUNCTIONS +***************************************************************************/ + +// is a given character a directory separator? + +constexpr bool is_directory_separator(char c) +{ +#if defined(WIN32) + return ('\\' == c) || ('/' == c) || (':' == c); +#else + return '/' == c; +#endif +} + } // namespace util diff --git a/src/lib/util/corestr.cpp b/src/lib/util/corestr.cpp index a2fef33a87a..5add3ed302f 100644 --- a/src/lib/util/corestr.cpp +++ b/src/lib/util/corestr.cpp @@ -10,6 +10,10 @@ #include "corestr.h" #include "osdcore.h" + +#include <algorithm> +#include <memory> + #include <ctype.h> #include <stdlib.h> @@ -236,3 +240,94 @@ int strreplace(std::string &str, const std::string& search, const std::string& r } return matches; } + +namespace util { + +/** + * @fn double edit_distance(std::u32string const &lhs, std::u32string const &rhs) + * + * @brief Compares strings and returns prefix-weighted similarity score (smaller is more similar). + * + * @param lhs First input. + * @param rhs Second input. + * + * @return Similarity score ranging from 0.0 (totally dissimilar) to 1.0 (identical). + */ + +double edit_distance(std::u32string const &lhs, std::u32string const &rhs) +{ + // based on Jaro-Winkler distance + // TODO: this breaks if the lengths don't fit in a long int, but that's not a big limitation + constexpr long MAX_PREFIX(4); + constexpr double PREFIX_WEIGHT(0.1); + constexpr double PREFIX_THRESHOLD(0.7); + + std::u32string const &longer((lhs.length() >= rhs.length()) ? lhs : rhs); + std::u32string const &shorter((lhs.length() < rhs.length()) ? lhs : rhs); + + // find matches + long const range((std::max)(long(longer.length() / 2) - 1, 0L)); + std::unique_ptr<long []> match_idx(std::make_unique<long []>(shorter.length())); + std::unique_ptr<bool []> match_flg(std::make_unique<bool []>(longer.length())); + std::fill_n(match_idx.get(), shorter.length(), -1); + std::fill_n(match_flg.get(), longer.length(), false); + long match_cnt(0); + for (long i = 0; shorter.length() > i; ++i) + { + char32_t const ch(shorter[i]); + long const n((std::min)(i + range + 1L, long(longer.length()))); + for (long j = (std::max)(i - range, 0L); n > j; ++j) + { + if (!match_flg[j] && (ch == longer[j])) + { + match_idx[i] = j; + match_flg[j] = true; + ++match_cnt; + break; + } + } + } + + // early exit if strings are very dissimilar + if (!match_cnt) + return 1.0; + + // now find transpositions + std::unique_ptr<char32_t []> ms(std::make_unique<char32_t []>(2 * match_cnt)); + std::fill_n(ms.get(), 2 * match_cnt, char32_t(0)); + char32_t *const ms1(&ms[0]); + char32_t *const ms2(&ms[match_cnt]); + for (long i = 0, j = 0; shorter.length() > i; ++i) + { + if (0 <= match_idx[i]) + ms1[j++] = shorter[i]; + } + match_idx.reset(); + for (long i = 0, j = 0; longer.length() > i; ++i) + { + if (match_flg[i]) + ms2[j++] = longer[i]; + } + match_flg.reset(); + long halftrans_cnt(0); + for (long i = 0; match_cnt > i; ++i) + { + if (ms1[i] != ms2[i]) + ++halftrans_cnt; + } + ms.reset(); + + // simple prefix detection + long prefix_len(0); + for (long i = 0; ((std::min)(long(shorter.length()), MAX_PREFIX) > i) && (lhs[i] == rhs[i]); ++i) + ++prefix_len; + + // do the weighting + double const m(match_cnt); + double const t(double(halftrans_cnt) / 2); + double const jaro(((m / lhs.length()) + (m / rhs.length()) + ((m - t) / m)) / 3); + double const jaro_winkler((PREFIX_THRESHOLD > jaro) ? jaro : (jaro + (PREFIX_WEIGHT * prefix_len * (1.0 - jaro)))); + return 1.0 - jaro_winkler; +} + +} // namespace util diff --git a/src/lib/util/corestr.h b/src/lib/util/corestr.h index d7734d50b29..c0bf4ef16d5 100644 --- a/src/lib/util/corestr.h +++ b/src/lib/util/corestr.h @@ -64,4 +64,11 @@ std::string &strmakeupper(std::string& str); std::string &strmakelower(std::string& str); int strreplace(std::string &str, const std::string& search, const std::string& replace); +namespace util { + +// based on Jaro-Winkler distance - returns value from 0.0 (totally dissimilar) to 1.0 (identical) +double edit_distance(std::u32string const &lhs, std::u32string const &rhs); + +} // namespace util + #endif // MAME_UTIL_CORESTR_H diff --git a/src/lib/util/unicode.cpp b/src/lib/util/unicode.cpp index 5151a1e101d..8e6478beee3 100644 --- a/src/lib/util/unicode.cpp +++ b/src/lib/util/unicode.cpp @@ -21,6 +21,67 @@ #include <locale> +namespace { + +//------------------------------------------------- +// internal_normalize_unicode - uses utf8proc to +// normalize unicode +//------------------------------------------------- + +std::string internal_normalize_unicode( + char const *s, + size_t length, + unicode_normalization_form normalization_form, + bool fold_case, + bool null_terminated) +{ + // convert the normalization form + int options; + switch (normalization_form) + { + case unicode_normalization_form::C: + options = UTF8PROC_STABLE | UTF8PROC_COMPOSE; + break; + case unicode_normalization_form::D: + options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE; + break; + case unicode_normalization_form::KC: + options = UTF8PROC_STABLE | UTF8PROC_COMPOSE | UTF8PROC_COMPAT; + break; + case unicode_normalization_form::KD: + options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE | UTF8PROC_COMPAT; + break; + default: + throw false; + } + + // perform case folding? + if (fold_case) + options |= UTF8PROC_CASEFOLD; + + // use NUL terminator to determine length? + if (null_terminated) + options |= UTF8PROC_NULLTERM; + + // invoke utf8proc + utf8proc_uint8_t *utf8proc_result(nullptr); + utf8proc_ssize_t const utf8proc_result_length(utf8proc_map(reinterpret_cast<utf8proc_uint8_t const *>(s), length, &utf8proc_result, utf8proc_option_t(options))); + + // conver the result + std::string result; + if (utf8proc_result) + { + if (utf8proc_result_length > 0) + result.assign(reinterpret_cast<char const *>(utf8proc_result), utf8proc_result_length); + free(utf8proc_result); + } + + return result; +} + +} // anonymous namespace + + //------------------------------------------------- // uchar_isvalid - return true if a given // character is a legitimate unicode character @@ -66,56 +127,53 @@ bool uchar_is_digit(char32_t uchar) int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count) { - char32_t c, minchar; - int auxlen, i; - char auxchar; - // validate parameters - if (utf8char == nullptr || count == 0) + if (!utf8char || !count) return 0; // start with the first byte - c = (unsigned char) *utf8char; + char32_t c = (unsigned char)*utf8char; count--; utf8char++; // based on that, determine how many additional bytes we need - if (c < 0x80) + char32_t minchar; + int auxlen; + if ((c & 0x80) == 0x00) { // unicode char 0x00000000 - 0x0000007F - c &= 0x7f; auxlen = 0; minchar = 0x00000000; } - else if (c >= 0xc0 && c < 0xe0) + else if ((c & 0xe0) == 0xc0) { // unicode char 0x00000080 - 0x000007FF c &= 0x1f; auxlen = 1; minchar = 0x00000080; } - else if (c >= 0xe0 && c < 0xf0) + else if ((c & 0xf0) == 0xe0) { // unicode char 0x00000800 - 0x0000FFFF c &= 0x0f; auxlen = 2; minchar = 0x00000800; } - else if (c >= 0xf0 && c < 0xf8) + else if ((c & 0xf8) == 0xf0) { // unicode char 0x00010000 - 0x001FFFFF c &= 0x07; auxlen = 3; minchar = 0x00010000; } - else if (c >= 0xf8 && c < 0xfc) + else if ((c & 0xfc) == 0xf8) { // unicode char 0x00200000 - 0x03FFFFFF c &= 0x03; auxlen = 4; minchar = 0x00200000; } - else if (c >= 0xfc && c < 0xfe) + else if ((c & 0xfe) == 0xfc) { // unicode char 0x04000000 - 0x7FFFFFFF c &= 0x01; @@ -133,9 +191,9 @@ int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count) return -1; // we now know how long the char is, now compute it - for (i = 0; i < auxlen; i++) + for (int i = 0; i < auxlen; i++) { - auxchar = utf8char[i]; + char32_t const auxchar = (unsigned char)utf8char[i]; // all auxillary chars must be between 0x80-0xbf if ((auxchar & 0xc0) != 0x80) @@ -206,6 +264,28 @@ int uchar_from_utf16f(char32_t *uchar, const char16_t *utf16char, size_t count) //------------------------------------------------- +// ustr_from_utf8 - convert a UTF-8 sequence into +// into a Unicode string +//------------------------------------------------- + +std::u32string ustr_from_utf8(const std::string &utf8str) +{ + std::u32string result; + char const *utf8char(utf8str.c_str()); + size_t remaining(utf8str.length()); + while (remaining) + { + char32_t ch; + int const consumed(uchar_from_utf8(&ch, utf8char, remaining)); + result.append(1, (consumed > 0) ? ch : char32_t(0x00fffdU)); + utf8char += (consumed > 0) ? consumed : 1; + remaining -= (consumed > 0) ? consumed : 1; + } + return result; +} + + +//------------------------------------------------- // utf8_from_uchar - convert a unicode character // into a UTF-8 sequence //------------------------------------------------- @@ -388,61 +468,13 @@ std::string utf8_from_wstring(const std::wstring &string) //------------------------------------------------- -// internal_normalize_unicode - uses utf8proc to -// normalize unicode -//------------------------------------------------- - -static std::string internal_normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool null_terminated) -{ - // convert the normalization form - int options; - switch (normalization_form) - { - case unicode_normalization_form::C: - options = UTF8PROC_STABLE | UTF8PROC_COMPOSE; - break; - case unicode_normalization_form::D: - options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE; - break; - case unicode_normalization_form::KC: - options = UTF8PROC_STABLE | UTF8PROC_COMPOSE | UTF8PROC_COMPAT; - break; - case unicode_normalization_form::KD: - options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE | UTF8PROC_COMPAT; - break; - default: - throw false; - } - - // was this null terminated? - if (null_terminated) - options |= UTF8PROC_NULLTERM; - - // invoke utf8proc - utf8proc_uint8_t *utf8proc_result; - utf8proc_ssize_t utf8proc_result_length = utf8proc_map((utf8proc_uint8_t *) s, length, &utf8proc_result, (utf8proc_option_t)options); - - // conver the result - std::string result; - if (utf8proc_result) - { - if (utf8proc_result_length > 0) - result = std::string((const char *)utf8proc_result, utf8proc_result_length); - free(utf8proc_result); - } - - return result; -} - - -//------------------------------------------------- // normalize_unicode - uses utf8proc to normalize // unicode //------------------------------------------------- -std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form) +std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form, bool fold_case) { - return internal_normalize_unicode(s.c_str(), s.length(), normalization_form, false); + return internal_normalize_unicode(s.c_str(), s.length(), normalization_form, fold_case, false); } @@ -451,9 +483,9 @@ std::string normalize_unicode(const std::string &s, unicode_normalization_form n // unicode //------------------------------------------------- -std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form) +std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form, bool fold_case) { - return internal_normalize_unicode(s, 0, normalization_form, true); + return internal_normalize_unicode(s, 0, normalization_form, fold_case, true); } @@ -462,9 +494,9 @@ std::string normalize_unicode(const char *s, unicode_normalization_form normaliz // unicode //------------------------------------------------- -std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form) +std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool fold_case) { - return internal_normalize_unicode(s, length, normalization_form, false); + return internal_normalize_unicode(s, length, normalization_form, fold_case, false); } diff --git a/src/lib/util/unicode.h b/src/lib/util/unicode.h index 5e30a74916e..46e1aec3496 100644 --- a/src/lib/util/unicode.h +++ b/src/lib/util/unicode.h @@ -14,14 +14,16 @@ singular 32-bit Unicode chars. ***************************************************************************/ +#ifndef MAME_LIB_UTIL_UNICODE_H +#define MAME_LIB_UTIL_UNICODE_H #pragma once -#ifndef UNICODE_H -#define UNICODE_H +#include "osdcore.h" + +#include <string> #include <stdlib.h> -#include "osdcore.h" @@ -95,6 +97,7 @@ bool uchar_is_digit(char32_t uchar); int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count); int uchar_from_utf16(char32_t *uchar, const char16_t *utf16char, size_t count); int uchar_from_utf16f(char32_t *uchar, const char16_t *utf16char, size_t count); +std::u32string ustr_from_utf8(const std::string &utf8str); // converting 32-bit Unicode chars to strings int utf8_from_uchar(char *utf8string, size_t count, char32_t uchar); @@ -107,9 +110,9 @@ std::wstring wstring_from_utf8(const std::string &utf8string); std::string utf8_from_wstring(const std::wstring &string); // unicode normalization -std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form); -std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form); -std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form); +std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form, bool fold_case = false); +std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form, bool fold_case = false); +std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool fold_case = false); // upper and lower case char32_t uchar_toupper(char32_t ch); @@ -137,4 +140,4 @@ bool utf8_is_valid_string(const char *utf8string); #define utf16le_from_uchar utf16f_from_uchar #endif -#endif /* UNICODE_H */ +#endif // MAME_LIB_UTIL_UNICODE_H |