/*
* md5 based hashtab
*
* Copyright (C) 2013-2019 Cisco Systems, Inc. and/or its affiliates. All rights reserved.
* Copyright (C) 2008-2013 Sourcefire, Inc.
*
* Authors: aCaB <acab@clamav.net>
*
* Uniq implements a structure that stores the count of duplicate items.
* The count can be retrieved by item name (if you know it).
* Additionally, you can retrieve the ascii md5 hash at the same time.
*
* This is essentially a tiny hash table of hashes.
* The hashes are in an array instead of dynamically added.
* This is faster than alloc'ing for each unique item added, * but means a max # of unique items must be defined at init.
*
* Example where:
* items = 6
* max_unique_items = 5
* cur_unique_items = 4
* md5 #1 has been added 3 times
* Two md5's start with the same 2 bytes (#0 and #3)
*
* idx:
* -00--01--02--03--04--05--06--07-...
* | 0 | 0 | 0 | 2 | 1 | 0 | 0 | ...
* ------------------------------...
*
* md5s:
* ------------------------------
* 0 | next: Address of #3
* | count: 1
* | md5: 0x01,0x98,0x23,0xa8,0xfd,...
* | name: "019823a8fd..."
* ------------------------------
* 1 | next: NULL
* | count: 3
* | md5: 0x03,0x98,0x23,0xa8,0xfd,...
* | name: "019823a8fd..."
* ------------------------------
* 2 | next: NULL
* | count: 1
* | md5: 0x01,0x98,0x23,0xa8,0xfd,...
* | name: "019823a8fd..."
* ------------------------------
* 3 | next: NULL
* | count: 1
* | md5: 0x01,0xdd,0x2f,0x87,0x6a,...
* | name: "01dd2f876a..."
* ------------------------------
* 4 | next: NULL
* | count: 0
* | md5: 0x00,0x00,0x00,0x00,0x00,...
* | name: "\0\0\0\0\0..."
* ------------------------------
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*
* 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, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*/
#ifndef _UNIQ_H
#define _UNIQ_H
#include "clamav.h"
#include "clamav-types.h"
/**
* @brief Store the count of each unique item.
*
* These elements are allocated as an array in struct uniq, but they are also
* linked together using the `next` pointers to form impromptu buckets,
* categorized using the first two bytes of each md5.
*/
struct UNIQMD5 {
struct UNIQMD5 *next; /**< Pointer to next UNIQMD5 where the first two bytes are the same. */
uint32_t count; /**< Number of times this item has been added. (# duplicates). */
uint8_t md5[16]; /**< Binary md5 hash of the item. */
char name[33]; /**< Ascii md5 hash of the item. */
};
/**
* @brief The main Uniq store structure.
*
* Includes array of uniq md5 hashes, and an index table to optimize searches
* into the hash array, categorized by the first two bytes of the md5.
*/
struct uniq {
struct UNIQMD5 *md5s; /**< Array of UNIQMD5 structs. */
uint32_t items; /**< Total # of items added (including duplicates) */
uint32_t cur_unique_items; /**< The # of md5s currently stored in the array. */
uint32_t max_unique_items; /**< The # of md5s that can be stored the array. */
uint32_t idx[256]; /**< Array of indices into the md5s array.
Each index represents a linked-list of md5s
sharing the common trait that the first two
bytes are the same. */
};
/**
* @brief Initialize a Uniq store to count the number of uniq string items.
*
* The Uniq store must be free'd with uniq_free().
* uniq_add()'s will fail if they exceed the number of unique strings initialized with count.
*
* @param count The max number of unique string items that may be added.
* @return struct uniq* A pointer to the Uniq store object. Will return NULL on failure.
*/
struct uniq *uniq_init(uint32_t);
/**
* @brief Free the Uniq store and associated memory.
*/
void uniq_free(struct uniq *);
/**
* @brief Add to the uniq (item md5) count.
*
* Adds an item to the list of known items.
* Increments the count if the item has been seen before.
* The optional rhash pointer will be valid until `uniq_free()` is called.
*
* @param U The Uniq count store.
* @param item (optional) The item to hash and count.
* @param item_len The length, in bytes, of the item. May be 0.
* @param[out] rhash (optional) A pointer to the item's md5 hash (in ascii).
* @param[out] count (optional) The number of times this unique item has been added.
* @return cl_error_t CL_SUCCESS if successful, else an error code.
*/
cl_error_t uniq_add(struct uniq *U, const char *item, uint32_t, char **rhash, uint32_t *count);
/**
* @brief Retrieve the number of times an item has been added to the Uniq count store.
*
* The optional rhash pointer will be valid until `uniq_free()` is called.
*
* @param U The Uniq count store.
* @param item (optional) The item to hash and count.
* @param item_len The length, in bytes, of the item. May be 0.
* @param[out] rhash (optional) A pointer to the item's md5 hash (in ascii).
* @param[out] count The number of times this unique item has been added.
* @return cl_error_t CL_SUCCESS if successful, else an error code.
*/
cl_error_t uniq_get(struct uniq *U, const char *item, uint32_t, char **rhash, uint32_t *count);
#endif