src/hashcomp.cpp

   1 /*
   2  * InspIRCd -- Internet Relay Chat Daemon
   3  *
   4  *   Copyright (C) 2019 linuxdaemon <linuxdaemon.irc@gmail.com>
   5  *   Copyright (C) 2013, 2018-2019 Sadie Powell <sadie@witchery.services>
   6  *   Copyright (C) 2013 Adam <Adam@anope.org>
   7  *   Copyright (C) 2012-2013, 2015-2016 Attila Molnar <attilamolnar@hush.com>
   8  *   Copyright (C) 2012 Robby <robby@chatbelgie.be>
   9  *   Copyright (C) 2009 Uli Schlachter <psychon@inspircd.org>
  10  *   Copyright (C) 2009 Daniel De Graaf <danieldg@inspircd.org>
  11  *   Copyright (C) 2008 Robin Burchell <robin+git@viroteck.net>
  12  *   Copyright (C) 2007 Dennis Friis <peavey@inspircd.org>
  13  *   Copyright (C) 2005-2007, 2010 Craig Edwards <brain@inspircd.org>
  14  *
  15  * This file is part of InspIRCd.  InspIRCd is free software: you can
  16  * redistribute it and/or modify it under the terms of the GNU General Public
  17  * License as published by the Free Software Foundation, version 2.
  18  *
  19  * This program is distributed in the hope that it will be useful, but WITHOUT
  20  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22  * details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  26  */
  27
  28
  29 #include "inspircd.h"
  30
  31 /******************************************************
  32  *
  33  * The hash functions of InspIRCd are the centrepoint
  34  * of the entire system. If these functions are
  35  * inefficient or wasteful, the whole program suffers
  36  * as a result. A lot of C programmers in the ircd
  37  * scene spend a lot of time debating (arguing) about
  38  * the best way to write hash functions to hash irc
  39  * nicknames, channels etc.
  40  * We are lucky as C++ developers as unordered_map does
  41  * a lot of this for us. It does intellegent memory
  42  * requests, bucketing, search functions, insertion
  43  * and deletion etc. All we have to do is write some
  44  * overloaded comparison and hash value operators which
  45  * cause it to act in an irc-like way. The features we
  46  * add to the standard hash_map are:
  47  *
  48  * Case insensitivity: The hash_map will be case
  49  * insensitive.
  50  *
  51  * Scandanavian Comparisons: The characters [, ], \ will
  52  * be considered the lowercase of {, } and |.
  53  *
  54  ******************************************************/
  55
  56
  57 /**
  58  * A case insensitive mapping of characters from upper case to lower case for
  59  * the ASCII character set.
  60  */
  61 unsigned const char ascii_case_insensitive_map[256] = {
  62         0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   // 0-9
  63         10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  // 10-19
  64         20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  // 20-29
  65         30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  // 30-39
  66         40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  // 40-49
  67         50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  // 50-59
  68         60,  61,  62,  63,  64,  97,  98,  99,  100, 101, // 60-69
  69         102, 103, 104, 105, 106, 107, 108, 109, 110, 111, // 70-79
  70         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, // 80-89
  71         122, 91,  92,  93,  94,  95,  96,  97,  98,  99,  // 90-99
  72         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, // 100-109
  73         110, 111, 112, 113, 114, 115, 116, 117, 118, 119, // 110-119
  74         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, // 120-129
  75         130, 131, 132, 133, 134, 135, 136, 137, 138, 139, // 130-139
  76         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, // 140-149
  77         150, 151, 152, 153, 154, 155, 156, 157, 158, 159, // 150-159
  78         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, // 160-169
  79         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, // 170-179
  80         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, // 180-189
  81         190, 191, 192, 193, 194, 195, 196, 197, 198, 199, // 190-199
  82         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, // 200-209
  83         210, 211, 212, 213, 214, 215, 216, 217, 218, 219, // 210-219
  84         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, // 220-229
  85         230, 231, 232, 233, 234, 235, 236, 237, 238, 239, // 230-249
  86         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, // 240-249
  87         250, 251, 252, 253, 254, 255,                     // 250-255
  88 };
  89
  90
  91
  92 /**
  93  * A case insensitive mapping of characters from upper case to lower case for
  94  * the character set of RFC 1459. This is identical to ASCII with the small
  95  * exception of {}| being considered to be the lower case equivalents of the
  96  * characters []\ respectively.
  97  */
  98 unsigned const char rfc_case_insensitive_map[256] = {
  99         0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   // 0-9
 100         10,  11,  12,  13,  14,  15,  16,  17,  18,  19,  // 10-19
 101         20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  // 20-29
 102         30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  // 30-39
 103         40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  // 40-49
 104         50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  // 50-59
 105         60,  61,  62,  63,  64,  97,  98,  99,  100, 101, // 60-69
 106         102, 103, 104, 105, 106, 107, 108, 109, 110, 111, // 70-79
 107         112, 113, 114, 115, 116, 117, 118, 119, 120, 121, // 80-89
 108         122, 123, 124, 125, 94,  95,  96,  97,  98,  99,  // 90-99
 109         100, 101, 102, 103, 104, 105, 106, 107, 108, 109, // 100-109
 110         110, 111, 112, 113, 114, 115, 116, 117, 118, 119, // 110-119
 111         120, 121, 122, 123, 124, 125, 126, 127, 128, 129, // 120-129
 112         130, 131, 132, 133, 134, 135, 136, 137, 138, 139, // 130-139
 113         140, 141, 142, 143, 144, 145, 146, 147, 148, 149, // 140-149
 114         150, 151, 152, 153, 154, 155, 156, 157, 158, 159, // 150-159
 115         160, 161, 162, 163, 164, 165, 166, 167, 168, 169, // 160-169
 116         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, // 170-179
 117         180, 181, 182, 183, 184, 185, 186, 187, 188, 189, // 180-189
 118         190, 191, 192, 193, 194, 195, 196, 197, 198, 199, // 190-199
 119         200, 201, 202, 203, 204, 205, 206, 207, 208, 209, // 200-209
 120         210, 211, 212, 213, 214, 215, 216, 217, 218, 219, // 210-219
 121         220, 221, 222, 223, 224, 225, 226, 227, 228, 229, // 220-229
 122         230, 231, 232, 233, 234, 235, 236, 237, 238, 239, // 230-239
 123         240, 241, 242, 243, 244, 245, 246, 247, 248, 249, // 240-249
 124         250, 251, 252, 253, 254, 255,                     // 250-255
 125 };
 126
 127 bool irc::equals(const std::string& s1, const std::string& s2)
 128 {
 129         const unsigned char* n1 = (const unsigned char*)s1.c_str();
 130         const unsigned char* n2 = (const unsigned char*)s2.c_str();
 131         for (; *n1 && *n2; n1++, n2++)
 132                 if (national_case_insensitive_map[*n1] != national_case_insensitive_map[*n2])
 133                         return false;
 134         return (national_case_insensitive_map[*n1] == national_case_insensitive_map[*n2]);
 135 }
 136
 137 size_t irc::find(const std::string& haystack, const std::string& needle)
 138 {
 139         // The haystack can't contain the needle if it is smaller than it.
 140         if (needle.length() > haystack.length())
 141                 return std::string::npos;
 142
 143         // The inner loop checks the characters between haystack_last and the end of the haystack.
 144         size_t haystack_last = haystack.length() - needle.length();
 145         for (size_t hpos = 0; hpos <= haystack_last; ++hpos)
 146         {
 147                 // Check for the needle at the current haystack position.
 148                 bool found = true;
 149                 for (size_t npos = 0; npos < needle.length(); ++npos)
 150                 {
 151                         if (national_case_insensitive_map[(unsigned char)needle[npos]] != national_case_insensitive_map[(unsigned char)haystack[hpos + npos]])
 152                         {
 153                                 // Uh-oh, characters at the current haystack position don't match.
 154                                 found = false;
 155                                 break;
 156                         }
 157                 }
 158
 159                 // The entire needle was found in the haystack!
 160                 if (found)
 161                         return hpos;
 162         }
 163
 164         // We didn't find anything.
 165         return std::string::npos;
 166 }
 167
 168
 169 bool irc::insensitive_swo::operator()(const std::string& a, const std::string& b) const
 170 {
 171         const unsigned char* charmap = national_case_insensitive_map;
 172         std::string::size_type asize = a.size();
 173         std::string::size_type bsize = b.size();
 174         std::string::size_type maxsize = std::min(asize, bsize);
 175
 176         for (std::string::size_type i = 0; i < maxsize; i++)
 177         {
 178                 unsigned char A = charmap[(unsigned char)a[i]];
 179                 unsigned char B = charmap[(unsigned char)b[i]];
 180                 if (A > B)
 181                         return false;
 182                 else if (A < B)
 183                         return true;
 184         }
 185         return (asize < bsize);
 186 }
 187
 188 size_t irc::insensitive::operator()(const std::string &s) const
 189 {
 190         /* XXX: NO DATA COPIES! :)
 191          * The hash function here is practically
 192          * a copy of the one in STL's hash_fun.h,
 193          * only with *x replaced with national_case_insensitive_map[*x].
 194          * This avoids a copy to use hash<const char*>
 195          */
 196         size_t t = 0;
 197         for (std::string::const_iterator x = s.begin(); x != s.end(); ++x) /* ++x not x++, as its faster */
 198                 t = 5 * t + national_case_insensitive_map[(unsigned char)*x];
 199         return t;
 200 }
 201
 202 irc::tokenstream::tokenstream(const std::string& msg, size_t start, size_t end)
 203         : message(msg, start, end)
 204         , position(0)
 205 {
 206 }
 207
 208 bool irc::tokenstream::GetMiddle(std::string& token)
 209 {
 210         // If we are past the end of the string we can't do anything.
 211         if (position >= message.length())
 212         {
 213                 token.clear();
 214                 return false;
 215         }
 216
 217         // If we can't find another separator this is the last token in the message.
 218         size_t separator = message.find(' ', position);
 219         if (separator == std::string::npos)
 220         {
 221                 token.assign(message, position, std::string::npos);
 222                 position = message.length();
 223                 return true;
 224         }
 225
 226         token.assign(message, position, separator - position);
 227         position = message.find_first_not_of(' ', separator);
 228         return true;
 229 }
 230
 231 bool irc::tokenstream::GetTrailing(std::string& token)
 232 {
 233         // If we are past the end of the string we can't do anything.
 234         if (position >= message.length())
 235         {
 236                 token.clear();
 237                 return false;
 238         }
 239
 240         // If this is true then we have a <trailing> token!
 241         if (message[position] == ':')
 242         {
 243                 token.assign(message, position + 1, std::string::npos);
 244                 position = message.length();
 245                 return true;
 246         }
 247
 248         // There is no <trailing> token so it must be a <middle> token.
 249         return GetMiddle(token);
 250 }
 251
 252 irc::sepstream::sepstream(const std::string& source, char separator, bool allowempty)
 253         : tokens(source), sep(separator), pos(0), allow_empty(allowempty)
 254 {
 255 }
 256
 257 bool irc::sepstream::GetToken(std::string &token)
 258 {
 259         if (this->StreamEnd())
 260         {
 261                 token.clear();
 262                 return false;
 263         }
 264
 265         if (!this->allow_empty)
 266         {
 267                 this->pos = this->tokens.find_first_not_of(this->sep, this->pos);
 268                 if (this->pos == std::string::npos)
 269                 {
 270                         this->pos = this->tokens.length() + 1;
 271                         token.clear();
 272                         return false;
 273                 }
 274         }
 275
 276         size_t p = this->tokens.find(this->sep, this->pos);
 277         if (p == std::string::npos)
 278                 p = this->tokens.length();
 279
 280         token.assign(tokens, this->pos, p - this->pos);
 281         this->pos = p + 1;
 282
 283         return true;
 284 }
 285
 286 const std::string irc::sepstream::GetRemaining()
 287 {
 288         return !this->StreamEnd() ? this->tokens.substr(this->pos) : "";
 289 }
 290
 291 bool irc::sepstream::StreamEnd()
 292 {
 293         return this->pos > this->tokens.length();
 294 }
 295
 296 bool irc::sepstream::Contains(const std::string& value)
 297 {
 298         std::string token;
 299         while (GetToken(token))
 300                 if (value == token)
 301                         return true;
 302
 303         return false;
 304 }
 305
 306 irc::portparser::portparser(const std::string &source, bool allow_overlapped)
 307         : sep(source), in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
 308 {
 309 }
 310
 311 bool irc::portparser::Overlaps(long val)
 312 {
 313         if (overlapped)
 314                 return false;
 315
 316         return (!overlap_set.insert(val).second);
 317 }
 318
 319 long irc::portparser::GetToken()
 320 {
 321         if (in_range > 0)
 322         {
 323                 in_range++;
 324                 if (in_range <= range_end)
 325                 {
 326                         if (!Overlaps(in_range))
 327                         {
 328                                 return in_range;
 329                         }
 330                         else
 331                         {
 332                                 while (((Overlaps(in_range)) && (in_range <= range_end)))
 333                                         in_range++;
 334
 335                                 if (in_range <= range_end)
 336                                         return in_range;
 337                         }
 338                 }
 339                 else
 340                         in_range = 0;
 341         }
 342
 343         std::string x;
 344         sep.GetToken(x);
 345
 346         if (x.empty())
 347                 return 0;
 348
 349         while (Overlaps(ConvToNum<long>(x)))
 350         {
 351                 if (!sep.GetToken(x))
 352                         return 0;
 353         }
 354
 355         std::string::size_type dash = x.rfind('-');
 356         if (dash != std::string::npos)
 357         {
 358                 std::string sbegin(x, 0, dash);
 359                 range_begin =  ConvToNum<long>(sbegin);
 360                 range_end =  ConvToNum<long>(x.c_str() + dash + 1);
 361
 362                 if ((range_begin > 0) && (range_end > 0) && (range_begin < 65536) && (range_end < 65536) && (range_begin < range_end))
 363                 {
 364                         in_range = range_begin;
 365                         return in_range;
 366                 }
 367                 else
 368                 {
 369                         /* Assume its just the one port */
 370                         return ConvToNum<long>(sbegin);
 371                 }
 372         }
 373         else
 374         {
 375                 return ConvToNum<long>(x);
 376         }
 377 }