* [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
@ 2025-04-20 13:08 Emma Worley
2025-04-20 13:08 ` [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility Emma Worley
2025-04-20 15:20 ` [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Nicolas George
0 siblings, 2 replies; 9+ messages in thread
From: Emma Worley @ 2025-04-20 13:08 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Emma Worley
Adds a general purpose hash table with the DXV encoder as an initial use case.
Signed-off-by: Emma Worley <emma@emma.gg>
---
libavutil/Makefile | 2 +
libavutil/hashtable.c | 192 ++++++++++++++++++++++++++++++++++++
libavutil/hashtable.h | 91 +++++++++++++++++
libavutil/tests/hashtable.c | 110 +++++++++++++++++++++
4 files changed, 395 insertions(+)
create mode 100644 libavutil/hashtable.c
create mode 100644 libavutil/hashtable.h
create mode 100644 libavutil/tests/hashtable.c
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 9ef118016b..43cb32c9d6 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -144,6 +144,7 @@ OBJS = adler32.o \
fixed_dsp.o \
frame.o \
hash.o \
+ hashtable.o \
hdr_dynamic_metadata.o \
hdr_dynamic_vivid_metadata.o \
hmac.o \
@@ -272,6 +273,7 @@ TESTPROGS = adler32 \
file \
fifo \
hash \
+ hashtable \
hmac \
hwdevice \
integer \
diff --git a/libavutil/hashtable.c b/libavutil/hashtable.c
new file mode 100644
index 0000000000..155a264665
--- /dev/null
+++ b/libavutil/hashtable.c
@@ -0,0 +1,192 @@
+/*
+ * Generic hashtable
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include "crc.h"
+#include "error.h"
+#include "mem.h"
+#include "hashtable.h"
+
+#define ALIGN _Alignof(size_t)
+
+struct AVHashtableContext {
+ size_t key_size;
+ size_t key_size_aligned;
+ size_t val_size;
+ size_t val_size_aligned;
+ size_t entry_size;
+ size_t max_entries;
+ size_t utilization;
+ const AVCRC *crc;
+ uint8_t *table;
+ uint8_t *swapbuf;
+};
+
+#define ENTRY_PSL(entry) (entry)
+#define ENTRY_OCC(entry) (ENTRY_PSL(entry) + FFALIGN(sizeof(size_t), ALIGN))
+#define ENTRY_KEY(entry) (ENTRY_OCC(entry) + FFALIGN(sizeof(size_t), ALIGN))
+#define ENTRY_VAL(entry) (ENTRY_KEY(entry) + ctx->key_size_aligned)
+
+#define KEYS_EQUAL(k1, k2) !memcmp(k1, k2, ctx->key_size)
+
+int av_hashtable_alloc(struct AVHashtableContext **ctx, size_t key_size, size_t val_size, size_t max_entries)
+{
+ struct AVHashtableContext *res = av_malloc(sizeof(struct AVHashtableContext));
+ if (!res)
+ return AVERROR(ENOMEM);
+ res->key_size = key_size;
+ res->key_size_aligned = FFALIGN(key_size, ALIGN);
+ res->val_size = val_size;
+ res->val_size_aligned = FFALIGN(val_size, ALIGN);
+ res->entry_size = FFALIGN(sizeof(size_t), ALIGN)
+ + FFALIGN(sizeof(size_t), ALIGN)
+ + res->key_size_aligned
+ + res->val_size_aligned;
+ res->max_entries = max_entries;
+ res->utilization = 0;
+ res->crc = av_crc_get_table(AV_CRC_32_IEEE);
+ if (!res->crc) {
+ av_hashtable_freep(&res);
+ return AVERROR_BUG;
+ }
+ res->table = av_calloc(res->max_entries, res->entry_size);
+ if (!res->table) {
+ av_hashtable_freep(&res);
+ return AVERROR(ENOMEM);
+ }
+ res->swapbuf = av_calloc(2, res->key_size_aligned + res->val_size_aligned);
+ if (!res->swapbuf) {
+ av_hashtable_freep(&res);
+ return AVERROR(ENOMEM);
+ }
+ *ctx = res;
+ return 0;
+}
+
+static size_t hash_key(const struct AVHashtableContext *ctx, const void *key)
+{
+ return av_crc(ctx->crc, 0, key, ctx->key_size) % ctx->max_entries;
+}
+
+int av_hashtable_get(const struct AVHashtableContext *ctx, const void *key, void *val)
+{
+ size_t hash = hash_key(ctx, key);
+
+ if (!ctx->utilization)
+ return 0;
+
+ for (size_t psl = 0; psl < ctx->max_entries; psl++) {
+ size_t wrapped_index = (hash + psl) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || *(size_t*)ENTRY_PSL(entry) < psl)
+ return 0;
+ if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
+ memcpy(val, ENTRY_VAL(entry), ctx->val_size);
+ return 1;
+ }
+ }
+ return 0;
+}
+
+int av_hashtable_set(struct AVHashtableContext *ctx, const void *key, const void *val)
+{
+ int swapping = 0;
+ size_t psl = 0;
+ size_t hash = hash_key(ctx, key);
+ uint8_t *set = ctx->swapbuf;
+ uint8_t *tmp = ctx->swapbuf + ctx->key_size_aligned + ctx->val_size_aligned;
+
+ memcpy(set, key, ctx->key_size);
+ memcpy(set + ctx->key_size_aligned, val, ctx->val_size);
+
+ for (size_t i = 0; i < ctx->max_entries; i++) {
+ size_t wrapped_index = (hash + i) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || (!swapping && KEYS_EQUAL(ENTRY_KEY(entry), set))) {
+ if (!*ENTRY_OCC(entry))
+ ctx->utilization++;
+ *(size_t*)ENTRY_PSL(entry) = psl;
+ *ENTRY_OCC(entry) = 1;
+ memcpy(ENTRY_KEY(entry), set, ctx->key_size_aligned + ctx->val_size);
+ return 1;
+ }
+ if (*(size_t*)ENTRY_PSL(entry) < psl) {
+ if (ctx->utilization == ctx->max_entries)
+ return 0;
+ swapping = 1;
+ // set needs to swap with entry
+ memcpy(tmp, ENTRY_KEY(entry), ctx->key_size_aligned + ctx->val_size);
+ memcpy(ENTRY_KEY(entry), set, ctx->key_size_aligned + ctx->val_size);
+ FFSWAP(uint8_t*, set, tmp);
+ FFSWAP(size_t, psl, *(size_t*)ENTRY_PSL(entry));
+ }
+ psl++;
+ }
+ return 0;
+}
+
+int av_hashtable_delete(struct AVHashtableContext *ctx, const void *key)
+{
+ uint8_t *next_entry;
+ size_t hash = hash_key(ctx, key);
+
+ if (!ctx->utilization)
+ return 0;
+
+ for (size_t psl = 0; psl < ctx->max_entries; psl++) {
+ size_t wrapped_index = (hash + psl) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || *(size_t*)ENTRY_PSL(entry) < psl)
+ return 0;
+ if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
+ *ENTRY_OCC(entry) = 0;
+ for (psl++; psl < ctx->max_entries; psl++) {
+ wrapped_index = (hash + psl) % ctx->max_entries;
+ next_entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(next_entry) || !*(size_t*)ENTRY_PSL(next_entry)) {
+ ctx->utilization--;
+ return 1;
+ }
+ memcpy(entry, next_entry, ctx->entry_size);
+ (*(size_t*)ENTRY_PSL(entry))--;
+ *ENTRY_OCC(next_entry) = 0;
+ entry = next_entry;
+ }
+ }
+ };
+ return 0;
+}
+
+void av_hashtable_clear(struct AVHashtableContext *ctx)
+{
+ memset(ctx->table, 0, ctx->entry_size * ctx->max_entries);
+}
+
+void av_hashtable_freep(struct AVHashtableContext **ctx)
+{
+ if (*ctx) {
+ av_freep(&(*ctx)->table);
+ av_freep(&(*ctx)->swapbuf);
+ }
+ av_freep(ctx);
+}
diff --git a/libavutil/hashtable.h b/libavutil/hashtable.h
new file mode 100644
index 0000000000..8ce6faafe3
--- /dev/null
+++ b/libavutil/hashtable.h
@@ -0,0 +1,91 @@
+/*
+ * Generic hashtable
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_HASHTABLE_H
+#define AVUTIL_HASHTABLE_H
+
+#include <stddef.h>
+
+/* Implements a hash table using Robin Hood open addressing.
+ * See: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
+ */
+
+struct AVHashtableContext;
+
+/**
+ * Creates a fixed-sized Robin Hood hash table.
+ *
+ * @param ctx context to allocate and initialize
+ * @param key_size size of key type in bytes
+ * @param val_size size of value type in bytes
+ * @param max_entries maximum number of key-value pairs to store
+ *
+ * @return zero on success, nonzero on error
+ */
+int av_hashtable_alloc(struct AVHashtableContext **ctx, size_t key_size, size_t val_size, size_t max_entries);
+
+/**
+ * Looks up a value from a hash table given a key.
+ *
+ * @param ctx hash table context
+ * @param key pointer to key data
+ * @param val destination pointer for value data
+ *
+ * @return 1 if the key is found, zero if the key is not found
+ */
+int av_hashtable_get(const struct AVHashtableContext *ctx, const void *key, void *val);
+
+/**
+ * Stores a value in a hash table given a key.
+ *
+ * @param ctx hash table context
+ * @param key pointer to key data
+ * @param val pointer for value data
+ *
+ * @return 1 if the key is written, zero if the key is not written due to the hash table reaching max capacity
+ */
+int av_hashtable_set(struct AVHashtableContext *ctx, const void *key, const void *val);
+
+/**
+ * Deletes a value from a hash table given a key.
+ *
+ * @param ctx hash table context
+ * @param key pointer to key data
+ *
+ * @return 1 if the key is deleted, zero if the key is not deleted due to not being found
+ */
+int av_hashtable_delete(struct AVHashtableContext *ctx, const void *key);
+
+/**
+ * Deletes all values from a hash table.
+ *
+ * @param ctx hash table context
+ */
+void av_hashtable_clear(struct AVHashtableContext *ctx);
+
+/**
+ * Frees a hash table.
+ *
+ * @param ctx hash table context
+ */
+void av_hashtable_freep(struct AVHashtableContext **ctx);
+
+#endif
diff --git a/libavutil/tests/hashtable.c b/libavutil/tests/hashtable.c
new file mode 100644
index 0000000000..1e37d7663b
--- /dev/null
+++ b/libavutil/tests/hashtable.c
@@ -0,0 +1,110 @@
+/*
+ * Generic hashtable tests
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stdint.h>
+
+#include "libavutil/avassert.h"
+#include "libavutil/hashtable.h"
+
+int main(void)
+{
+ struct AVHashtableContext *ctx;
+ uint8_t k;
+ uint64_t v;
+
+ // impossibly large allocation should fail gracefully
+ av_assert0(av_hashtable_alloc(&ctx, -1, -1, -1) < 0);
+
+ // hashtable can store up to 3 uint8_t->uint64_t entries
+ av_assert0(!av_hashtable_alloc(&ctx, sizeof(k), sizeof(v), 3));
+
+ // unsuccessful deletes return 0
+ k = 1;
+ av_assert0(!av_hashtable_delete(ctx, &k));
+
+ // unsuccessful gets return 0
+ k = 1;
+ av_assert0(!av_hashtable_get(ctx, &k, &v));
+
+ // successful sets returns 1
+ k = 1;
+ v = 1;
+ av_assert0(av_hashtable_set(ctx, &k, &v));
+
+ // get should now contain 1
+ k = 1;
+ v = 0;
+ av_assert0(av_hashtable_get(ctx, &k, &v));
+ av_assert0(v == 1);
+
+ // updating sets should return 1
+ k = 1;
+ v = 2;
+ av_assert0(av_hashtable_set(ctx, &k, &v));
+
+ // get should now contain 2
+ k = 1;
+ v = 0;
+ av_assert0(av_hashtable_get(ctx, &k, &v));
+ av_assert0(v == 2);
+
+ // fill the table
+ k = 2;
+ v = 2;
+ av_assert0(av_hashtable_set(ctx, &k, &v));
+ k = 3;
+ v = 3;
+ av_assert0(av_hashtable_set(ctx, &k, &v));
+
+ // inserting sets on a full table should return 0
+ k = 4;
+ v = 4;
+ av_assert0(!av_hashtable_set(ctx, &k, &v));
+
+ // updating sets on a full table should return 1
+ k = 1;
+ v = 4;
+ av_assert0(av_hashtable_set(ctx, &k, &v));
+ v = 0;
+ av_assert0(av_hashtable_get(ctx, &k, &v));
+ av_assert0(v == 4);
+
+ // successful deletes should return 1
+ k = 1;
+ av_assert0(av_hashtable_delete(ctx, &k));
+
+ // get should now return 0
+ av_assert0(!av_hashtable_get(ctx, &k, &v));
+
+ // sanity check remaining keys
+ k = 2;
+ v = 0;
+ av_assert0(av_hashtable_get(ctx, &k, &v));
+ av_assert0(v == 2);
+ k = 3;
+ v = 0;
+ av_assert0(av_hashtable_get(ctx, &k, &v));
+ av_assert0(v == 3);
+
+ av_hashtable_freep(&ctx);
+
+ return 0;
+}
--
2.48.0
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility
2025-04-20 13:08 [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Emma Worley
@ 2025-04-20 13:08 ` Emma Worley
2025-04-20 15:10 ` Nicolas George
2025-04-20 15:15 ` James Almer
2025-04-20 15:20 ` [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Nicolas George
1 sibling, 2 replies; 9+ messages in thread
From: Emma Worley @ 2025-04-20 13:08 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Emma Worley
Offers a modest performance gain due to the switch from naive linear
probling to robin hood, as well as improved compatibility with Resolume.
Signed-off-by: Emma Worley <emma@emma.gg>
---
libavcodec/dxvenc.c | 190 +++++++++++++-----------------------
tests/ref/fate/dxv3enc-dxt1 | 2 +-
2 files changed, 69 insertions(+), 123 deletions(-)
diff --git a/libavcodec/dxvenc.c b/libavcodec/dxvenc.c
index 808d8daedb..b2972435a2 100644
--- a/libavcodec/dxvenc.c
+++ b/libavcodec/dxvenc.c
@@ -21,7 +21,7 @@
#include <stdint.h>
-#include "libavutil/crc.h"
+#include "libavutil/hashtable.h"
#include "libavutil/imgutils.h"
#include "libavutil/mem.h"
#include "libavutil/opt.h"
@@ -34,77 +34,19 @@
#define DXV_HEADER_LENGTH 12
+/*
+ * Resolume will refuse to display frames that are not padded to 16x16 pixels.
+ */
+#define DXV_PAD(x) (x + 15 & ~15)
+
/*
* DXV uses LZ-like back-references to avoid copying words that have already
* appeared in the decompressed stream. Using a simple hash table (HT)
* significantly speeds up the lookback process while encoding.
*/
-#define LOOKBACK_HT_ELEMS 0x40000
+#define LOOKBACK_HT_ELEMS 0x20202
#define LOOKBACK_WORDS 0x20202
-typedef struct HTEntry {
- uint32_t key;
- uint32_t pos;
-} HTEntry;
-
-static void ht_init(HTEntry *ht)
-{
- for (size_t i = 0; i < LOOKBACK_HT_ELEMS; i++) {
- ht[i].pos = -1;
- }
-}
-
-static uint32_t ht_lookup_and_upsert(HTEntry *ht, const AVCRC *hash_ctx,
- uint32_t key, uint32_t pos)
-{
- uint32_t ret = -1;
- size_t hash = av_crc(hash_ctx, 0, (uint8_t*)&key, 4) % LOOKBACK_HT_ELEMS;
- for (size_t i = hash; i < hash + LOOKBACK_HT_ELEMS; i++) {
- size_t wrapped_index = i % LOOKBACK_HT_ELEMS;
- HTEntry *entry = &ht[wrapped_index];
- if (entry->key == key || entry->pos == -1) {
- ret = entry->pos;
- entry->key = key;
- entry->pos = pos;
- break;
- }
- }
- return ret;
-}
-
-static void ht_delete(HTEntry *ht, const AVCRC *hash_ctx,
- uint32_t key, uint32_t pos)
-{
- HTEntry *removed_entry = NULL;
- size_t removed_hash;
- size_t hash = av_crc(hash_ctx, 0, (uint8_t*)&key, 4) % LOOKBACK_HT_ELEMS;
-
- for (size_t i = hash; i < hash + LOOKBACK_HT_ELEMS; i++) {
- size_t wrapped_index = i % LOOKBACK_HT_ELEMS;
- HTEntry *entry = &ht[wrapped_index];
- if (entry->pos == -1)
- return;
- if (removed_entry) {
- size_t candidate_hash = av_crc(hash_ctx, 0, (uint8_t*)&entry->key, 4) % LOOKBACK_HT_ELEMS;
- if ((wrapped_index > removed_hash && (candidate_hash <= removed_hash || candidate_hash > wrapped_index)) ||
- (wrapped_index < removed_hash && (candidate_hash <= removed_hash && candidate_hash > wrapped_index))) {
- *removed_entry = *entry;
- entry->pos = -1;
- removed_entry = entry;
- removed_hash = wrapped_index;
- }
- } else if (entry->key == key) {
- if (entry->pos <= pos) {
- entry->pos = -1;
- removed_entry = entry;
- removed_hash = wrapped_index;
- } else {
- return;
- }
- }
- }
-}
-
typedef struct DXVEncContext {
AVClass *class;
@@ -121,10 +63,9 @@ typedef struct DXVEncContext {
DXVTextureFormat tex_fmt;
int (*compress_tex)(AVCodecContext *avctx);
- const AVCRC *crc_ctx;
-
- HTEntry color_lookback_ht[LOOKBACK_HT_ELEMS];
- HTEntry lut_lookback_ht[LOOKBACK_HT_ELEMS];
+ struct AVHashtableContext *color_ht;
+ struct AVHashtableContext *lut_ht;
+ struct AVHashtableContext *combo_ht;
} DXVEncContext;
/* Converts an index offset value to a 2-bit opcode and pushes it to a stream.
@@ -159,58 +100,63 @@ static int dxv_compress_dxt1(AVCodecContext *avctx)
DXVEncContext *ctx = avctx->priv_data;
PutByteContext *pbc = &ctx->pbc;
void *value;
- uint32_t color, lut, idx, color_idx, lut_idx, prev_pos, state = 16, pos = 2, op = 0;
+ uint64_t combo;
+ uint32_t color, lut, idx, combo_idx, prev_pos, old_pos, state = 16, pos = 0, op = 0;
- ht_init(ctx->color_lookback_ht);
- ht_init(ctx->lut_lookback_ht);
+ av_hashtable_clear(ctx->color_ht);
+ av_hashtable_clear(ctx->lut_ht);
+ av_hashtable_clear(ctx->combo_ht);
+
+ av_hashtable_set(ctx->combo_ht, ctx->tex_data, &pos);
bytestream2_put_le32(pbc, AV_RL32(ctx->tex_data));
+ av_hashtable_set(ctx->color_ht, ctx->tex_data, &pos);
+ pos++;
bytestream2_put_le32(pbc, AV_RL32(ctx->tex_data + 4));
-
- ht_lookup_and_upsert(ctx->color_lookback_ht, ctx->crc_ctx, AV_RL32(ctx->tex_data), 0);
- ht_lookup_and_upsert(ctx->lut_lookback_ht, ctx->crc_ctx, AV_RL32(ctx->tex_data + 4), 1);
+ av_hashtable_set(ctx->lut_ht, ctx->tex_data + 4, &pos);
+ pos++;
while (pos + 2 <= ctx->tex_size / 4) {
- idx = 0;
-
- color = AV_RL32(ctx->tex_data + pos * 4);
- prev_pos = ht_lookup_and_upsert(ctx->color_lookback_ht, ctx->crc_ctx, color, pos);
- color_idx = prev_pos != -1 ? pos - prev_pos : 0;
+ combo = AV_RL64(ctx->tex_data + pos * 4);
+ combo_idx = av_hashtable_get(ctx->combo_ht, &combo, &prev_pos) ? pos - prev_pos : 0;
+ idx = combo_idx;
+ PUSH_OP(2);
if (pos >= LOOKBACK_WORDS) {
- uint32_t old_pos = pos - LOOKBACK_WORDS;
- uint32_t old_color = AV_RL32(ctx->tex_data + old_pos * 4);
- ht_delete(ctx->color_lookback_ht, ctx->crc_ctx, old_color, old_pos);
+ old_pos = pos - LOOKBACK_WORDS;
+ if (av_hashtable_get(ctx->combo_ht, ctx->tex_data + old_pos * 4, &prev_pos) && prev_pos <= old_pos)
+ av_hashtable_delete(ctx->combo_ht, ctx->tex_data + old_pos * 4);
}
- pos++;
+ av_hashtable_set(ctx->combo_ht, &combo, &pos);
- lut = AV_RL32(ctx->tex_data + pos * 4);
- if (color_idx && lut == AV_RL32(ctx->tex_data + (pos - color_idx) * 4)) {
- idx = color_idx;
- } else {
- idx = 0;
- prev_pos = ht_lookup_and_upsert(ctx->lut_lookback_ht, ctx->crc_ctx, lut, pos);
- lut_idx = prev_pos != -1 ? pos - prev_pos : 0;
+ color = AV_RL32(ctx->tex_data + pos * 4);
+ if (!combo_idx) {
+ idx = av_hashtable_get(ctx->color_ht, &color, &prev_pos) ? pos - prev_pos : 0;
+ PUSH_OP(2);
+ if (!idx)
+ bytestream2_put_le32(pbc, color);
}
if (pos >= LOOKBACK_WORDS) {
- uint32_t old_pos = pos - LOOKBACK_WORDS;
- uint32_t old_lut = AV_RL32(ctx->tex_data + old_pos * 4);
- ht_delete(ctx->lut_lookback_ht, ctx->crc_ctx, old_lut, old_pos);
+ old_pos = pos - LOOKBACK_WORDS;
+ if (av_hashtable_get(ctx->color_ht, ctx->tex_data + old_pos * 4, &prev_pos) && prev_pos <= old_pos)
+ av_hashtable_delete(ctx->color_ht, ctx->tex_data + old_pos * 4);
}
+ av_hashtable_set(ctx->color_ht, &color, &pos);
pos++;
- PUSH_OP(2);
-
- if (!idx) {
- idx = color_idx;
- PUSH_OP(2);
- if (!idx)
- bytestream2_put_le32(pbc, color);
-
- idx = lut_idx;
+ lut = AV_RL32(ctx->tex_data + pos * 4);
+ if (!combo_idx) {
+ idx = av_hashtable_get(ctx->lut_ht, &lut, &prev_pos) ? pos - prev_pos : 0;
PUSH_OP(2);
if (!idx)
- bytestream2_put_le32(pbc, lut);
+ bytestream2_put_le32(pbc, lut);
}
+ if (pos >= LOOKBACK_WORDS) {
+ old_pos = pos - LOOKBACK_WORDS;
+ if (av_hashtable_get(ctx->lut_ht, ctx->tex_data + old_pos * 4, &prev_pos) && prev_pos <= old_pos)
+ av_hashtable_delete(ctx->lut_ht, ctx->tex_data + old_pos * 4);
+ }
+ av_hashtable_set(ctx->lut_ht, &lut, &pos);
+ pos++;
}
return 0;
@@ -234,8 +180,8 @@ static int dxv_encode(AVCodecContext *avctx, AVPacket *pkt,
ctx->enc.tex_data.out = ctx->tex_data;
ctx->enc.frame_data.in = frame->data[0];
ctx->enc.stride = frame->linesize[0];
- ctx->enc.width = avctx->width;
- ctx->enc.height = avctx->height;
+ ctx->enc.width = DXV_PAD(avctx->width);
+ ctx->enc.height = DXV_PAD(avctx->height);
ff_texturedsp_exec_compress_threads(avctx, &ctx->enc);
} else {
/* unimplemented: YCoCg formats */
@@ -275,14 +221,6 @@ static av_cold int dxv_init(AVCodecContext *avctx)
return ret;
}
- if (avctx->width % TEXTURE_BLOCK_W || avctx->height % TEXTURE_BLOCK_H) {
- av_log(avctx,
- AV_LOG_ERROR,
- "Video size %dx%d is not multiple of "AV_STRINGIFY(TEXTURE_BLOCK_W)"x"AV_STRINGIFY(TEXTURE_BLOCK_H)".\n",
- avctx->width, avctx->height);
- return AVERROR_INVALIDDATA;
- }
-
ff_texturedspenc_init(&texdsp);
switch (ctx->tex_fmt) {
@@ -296,21 +234,25 @@ static av_cold int dxv_init(AVCodecContext *avctx)
return AVERROR_INVALIDDATA;
}
ctx->enc.raw_ratio = 16;
- ctx->tex_size = avctx->width / TEXTURE_BLOCK_W *
- avctx->height / TEXTURE_BLOCK_H *
+ ctx->tex_size = DXV_PAD(avctx->width) / TEXTURE_BLOCK_W *
+ DXV_PAD(avctx->height) / TEXTURE_BLOCK_H *
ctx->enc.tex_ratio;
- ctx->enc.slice_count = av_clip(avctx->thread_count, 1, avctx->height / TEXTURE_BLOCK_H);
+ ctx->enc.slice_count = av_clip(avctx->thread_count, 1, DXV_PAD(avctx->height) / TEXTURE_BLOCK_H);
ctx->tex_data = av_malloc(ctx->tex_size);
if (!ctx->tex_data) {
return AVERROR(ENOMEM);
}
- ctx->crc_ctx = av_crc_get_table(AV_CRC_32_IEEE);
- if (!ctx->crc_ctx) {
- av_log(avctx, AV_LOG_ERROR, "Could not initialize CRC table.\n");
- return AVERROR_BUG;
- }
+ ret = av_hashtable_alloc(&ctx->color_ht, sizeof(uint32_t), sizeof(uint32_t), LOOKBACK_HT_ELEMS);
+ if (ret < 0)
+ return ret;
+ ret = av_hashtable_alloc(&ctx->lut_ht, sizeof(uint32_t), sizeof(uint32_t), LOOKBACK_HT_ELEMS);
+ if (ret < 0)
+ return ret;
+ ret = av_hashtable_alloc(&ctx->combo_ht, sizeof(uint64_t), sizeof(uint32_t), LOOKBACK_HT_ELEMS);
+ if (ret < 0)
+ return ret;
return 0;
}
@@ -321,6 +263,10 @@ static av_cold int dxv_close(AVCodecContext *avctx)
av_freep(&ctx->tex_data);
+ av_hashtable_freep(&ctx->color_ht);
+ av_hashtable_freep(&ctx->lut_ht);
+ av_hashtable_freep(&ctx->combo_ht);
+
return 0;
}
diff --git a/tests/ref/fate/dxv3enc-dxt1 b/tests/ref/fate/dxv3enc-dxt1
index 74849a8031..1e1b86aa6c 100644
--- a/tests/ref/fate/dxv3enc-dxt1
+++ b/tests/ref/fate/dxv3enc-dxt1
@@ -3,4 +3,4 @@
#codec_id 0: dxv
#dimensions 0: 1920x1080
#sar 0: 1/1
-0, 0, 0, 1, 76521, 0xed387a5e
+0, 0, 0, 1, 76563, 0x6b028fff
--
2.48.0
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility
2025-04-20 13:08 ` [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility Emma Worley
@ 2025-04-20 15:10 ` Nicolas George
2025-04-20 15:15 ` James Almer
1 sibling, 0 replies; 9+ messages in thread
From: Nicolas George @ 2025-04-20 15:10 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Emma Worley (HE12025-04-20):
> Subject: Re: [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to
> lavu hashtable and improve Resolume compatibility
Thanks for the patch. Are the two indissociably linked? I have trouble
imagining it.
Unless there is a strong reason making it impossible, it should be two
separate commits:
- one that refactors the code but does not change the output at all,
FATE tests guaranteeing it;
- one that improve the encoding and changes the output.
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility
2025-04-20 13:08 ` [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility Emma Worley
2025-04-20 15:10 ` Nicolas George
@ 2025-04-20 15:15 ` James Almer
1 sibling, 0 replies; 9+ messages in thread
From: James Almer @ 2025-04-20 15:15 UTC (permalink / raw)
To: ffmpeg-devel
[-- Attachment #1.1.1: Type: text/plain, Size: 288 bytes --]
On 4/20/2025 10:08 AM, Emma Worley wrote:
> Offers a modest performance gain due to the switch from naive linear
> probling to robin hood, as well as improved compatibility with Resolume.
A few numbers would be nice since you're adding new public API and a lot
of code changes.
[-- Attachment #1.2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 495 bytes --]
[-- Attachment #2: Type: text/plain, Size: 251 bytes --]
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
2025-04-20 13:08 [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Emma Worley
2025-04-20 13:08 ` [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility Emma Worley
@ 2025-04-20 15:20 ` Nicolas George
1 sibling, 0 replies; 9+ messages in thread
From: Nicolas George @ 2025-04-20 15:20 UTC (permalink / raw)
To: FFmpeg development discussions and patches
Emma Worley (HE12025-04-20):
> Adds a general purpose hash table with the DXV encoder as an initial use case.
A hash table for flat binary objects of constant size, both keys and
values, does not feel very general-purpose to me. Probably better to
keep it directly in the DXV encoder for now, until other use cases are
found.
(An inventory of all the data structures and algorithms that are
implemented once for a specific component would be nice, though.)
Regards,
--
Nicolas George
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
2024-02-06 5:00 ` Connor Worley
@ 2024-02-06 10:13 ` Connor Worley
0 siblings, 0 replies; 9+ messages in thread
From: Connor Worley @ 2024-02-06 10:13 UTC (permalink / raw)
To: FFmpeg development discussions and patches
NVM, I see what you mean by pointerswaps.
On Mon, Feb 5, 2024 at 9:00 PM Connor Worley <connorbworley@gmail.com>
wrote:
> On Mon, Feb 5, 2024 at 3:58 AM Andreas Rheinhardt <
> andreas.rheinhardt@outlook.com> wrote:
>
>> Connor Worley:
>> > + memcpy(ctx->tmp_key, ctx->set_key, ctx->key_size);
>> > + memcpy(ctx->tmp_val, ctx->set_val, ctx->val_size);
>>
>> Given that set_key/val are overwritten below, these two can be done via
>> pointerswaps.
>
>
> I don't quite follow, can you elaborate on this part?
> --
> Connor Worley
>
--
Connor Worley
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
2024-02-05 12:00 ` Andreas Rheinhardt
@ 2024-02-06 5:00 ` Connor Worley
2024-02-06 10:13 ` Connor Worley
0 siblings, 1 reply; 9+ messages in thread
From: Connor Worley @ 2024-02-06 5:00 UTC (permalink / raw)
To: FFmpeg development discussions and patches
On Mon, Feb 5, 2024 at 3:58 AM Andreas Rheinhardt <
andreas.rheinhardt@outlook.com> wrote:
> Connor Worley:
> > + memcpy(ctx->tmp_key, ctx->set_key, ctx->key_size);
> > + memcpy(ctx->tmp_val, ctx->set_val, ctx->val_size);
>
> Given that set_key/val are overwritten below, these two can be done via
> pointerswaps.
I don't quite follow, can you elaborate on this part?
--
Connor Worley
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
2024-02-05 5:27 Connor Worley
@ 2024-02-05 12:00 ` Andreas Rheinhardt
2024-02-06 5:00 ` Connor Worley
0 siblings, 1 reply; 9+ messages in thread
From: Andreas Rheinhardt @ 2024-02-05 12:00 UTC (permalink / raw)
To: ffmpeg-devel
Connor Worley:
> Signed-off-by: Connor Worley <connorbworley@gmail.com>
> ---
> libavutil/Makefile | 2 +
> libavutil/hashtable.c | 172 ++++++++++++++++++++++++++++++++++++
> libavutil/hashtable.h | 62 +++++++++++++
> libavutil/tests/hashtable.c | 104 ++++++++++++++++++++++
> 4 files changed, 340 insertions(+)
> create mode 100644 libavutil/hashtable.c
> create mode 100644 libavutil/hashtable.h
> create mode 100644 libavutil/tests/hashtable.c
>
> diff --git a/libavutil/Makefile b/libavutil/Makefile
> index e7709b97d0..be75d464fc 100644
> --- a/libavutil/Makefile
> +++ b/libavutil/Makefile
> @@ -138,6 +138,7 @@ OBJS = adler32.o \
> fixed_dsp.o \
> frame.o \
> hash.o \
> + hashtable.o \
> hdr_dynamic_metadata.o \
> hdr_dynamic_vivid_metadata.o \
> hmac.o \
> @@ -251,6 +252,7 @@ TESTPROGS = adler32 \
> file \
> fifo \
> hash \
> + hashtable \
> hmac \
> hwdevice \
> integer \
> diff --git a/libavutil/hashtable.c b/libavutil/hashtable.c
> new file mode 100644
> index 0000000000..fb0f0aae99
> --- /dev/null
> +++ b/libavutil/hashtable.c
> @@ -0,0 +1,172 @@
> +/*
> + * Generic hashtable
> + * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg 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.
> + *
> + * FFmpeg 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 FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <stdint.h>
> +
> +#include "error.h"
> +#include "mem.h"
> +#include "hashtable.h"
> +#include "string.h"
We don't have a string.h header; the string.h from the C stdlib should
of course be included via <>.
> +
> +#define ENTRY_OCC(entry) (entry)
> +#define ENTRY_KEY(entry) (ENTRY_OCC(entry) + 1)
> +#define ENTRY_VAL(entry) (ENTRY_KEY(entry) + ctx->key_size)
> +#define ENTRY_PSL(entry) (size_t*) (ENTRY_VAL(entry) + ctx->val_size)
Unaligned access. You need to align entry_size to the required alignment
of size_t and put this at the start of it the entry to avoid this.
Apart from that: The layout of your entries implies that only two
members are at a fixed offset from the start, so that accessing val and
psl requires actual additions. If you make it psl, occ, key, val, then
only val has a variable offset. This should be beneficial given that it
is the less accessed of key and val (in particular if you combine
several memcpy calls as I outline below).
(This is of course a good reason not to make the layout of the entries
public.)
> +
> +#define KEYS_EQUAL(k1, k2) !memcmp(k1, k2, ctx->key_size)
> +
> +int av_hashtable_init(AVHashtableContext* ctx, size_t key_size, size_t val_size, size_t max_entries)
> +{
> + ctx->key_size = key_size;
> + ctx->val_size = val_size;
> + ctx->entry_size = 1 + key_size + val_size + sizeof(size_t);
> + ctx->max_entries = max_entries;
> + ctx->utilization = 0;
> + ctx->crc = av_crc_get_table(AV_CRC_32_IEEE);
> + if (!ctx->crc)
> + return AVERROR_BUG;
> + ctx->table = av_mallocz(ctx->entry_size * max_entries);
av_calloc()
> + if (!ctx->table)
> + return AVERROR(ENOMEM);
> + ctx->set_key = av_malloc(key_size);
> + if (!ctx->set_key)
> + return AVERROR(ENOMEM);
> + ctx->set_val = av_malloc(key_size);
Should be val_size. Your test should test scenarios with key_size !=
val_size to uncover this.
> + if (!ctx->set_val)
> + return AVERROR(ENOMEM);
> + ctx->tmp_key = av_malloc(key_size);
> + if (!ctx->tmp_key)
> + return AVERROR(ENOMEM);
> + ctx->tmp_val = av_malloc(val_size);
> + if (!ctx->tmp_val)
> + return AVERROR(ENOMEM);
> + return 0;
> +}
(There are btw issues with what happens on error here, but we can ignore
this in the first round.)
> +
> +static size_t hash_key(const AVHashtableContext* ctx, const void* key)
> +{
> + return av_crc(ctx->crc, 0, key, ctx->key_size) % ctx->max_entries;
> +}
> +
> +int av_hashtable_get(const AVHashtableContext* ctx, const void* key, void* val)
> +{
> + size_t hash = hash_key(ctx, key);
> +
> + if (!ctx->utilization)
> + return 0;
> +
> + for (size_t psl = 0; psl < ctx->max_entries; psl++) {
> + size_t wrapped_index = (hash + psl) % ctx->max_entries;
> + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
> + if (!*ENTRY_OCC(entry) || *ENTRY_PSL(entry) < psl)
> + return 0;
> + if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
> + memcpy(val, ENTRY_VAL(entry), ctx->val_size);
> + return 1;
> + }
> + }
> + return 0;
> +}
> +
> +int av_hashtable_set(AVHashtableContext* ctx, const void* key, const void* val)
> +{
> + int swapping = 0;
> + size_t psl = 0;
> + size_t hash = hash_key(ctx, key);
> +
> + memcpy(ctx->set_key, key, ctx->key_size);
> + memcpy(ctx->set_val, val, ctx->val_size);
> +
> + for (size_t i = 0; i < ctx->max_entries; i++) {
> + size_t wrapped_index = (hash + i) % ctx->max_entries;
> + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
> + if (!*ENTRY_OCC(entry) || (!swapping && KEYS_EQUAL(ENTRY_KEY(entry), ctx->set_key))) {
> + if (!*ENTRY_OCC(entry))
> + ctx->utilization++;
> + *ENTRY_OCC(entry) = 1;
> + memcpy(ENTRY_KEY(entry), ctx->set_key, ctx->key_size);
> + memcpy(ENTRY_VAL(entry), ctx->set_val, ctx->val_size);
> + *ENTRY_PSL(entry) = psl;
> + return 1;
> + }
> + if (*ENTRY_PSL(entry) < psl) {
> + if (ctx->utilization == ctx->max_entries)
> + return 0;
> + swapping = 1;
> + memcpy(ctx->tmp_key, ctx->set_key, ctx->key_size);
> + memcpy(ctx->tmp_val, ctx->set_val, ctx->val_size);
Given that set_key/val are overwritten below, these two can be done via
pointerswaps.
> + memcpy(ctx->set_key, ENTRY_KEY(entry), ctx->key_size);
> + memcpy(ctx->set_val, ENTRY_VAL(entry), ctx->val_size);
> + memcpy(ENTRY_KEY(entry), ctx->tmp_key, ctx->key_size);
> + memcpy(ENTRY_VAL(entry), ctx->tmp_val, ctx->val_size);
> + FFSWAP(size_t, psl, *ENTRY_PSL(entry));
If you allocated foo_key and foo_val jointly, you can combine these
memcpy's. In fact, you can allocate all four them jointly with a
key-val-key-val layout and only keep one pointer in the context. You
would then use an uint8_t *set, *val pointers on the stack of this
function that are initialized at the beginning of this function.
> + }
> + psl++;
> + }
> + return 0;
> +}
> +
> +int av_hashtable_delete(AVHashtableContext* ctx, const void* key)
> +{
> + uint8_t *next_entry;
> + size_t hash = hash_key(ctx, key);
> +
> + if (!ctx->utilization)
> + return 0;
> +
> + for (size_t psl = 0; psl < ctx->max_entries; psl++) {
> + size_t wrapped_index = (hash + psl) % ctx->max_entries;
> + uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
> + if (!*ENTRY_OCC(entry) || *ENTRY_PSL(entry) < psl)
> + return 0;
> + if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
> + *ENTRY_OCC(entry) = 0;
> + for (psl++; psl < ctx->max_entries; psl++) {
> + wrapped_index = (hash + psl) % ctx->max_entries;
> + next_entry = ctx->table + wrapped_index * ctx->entry_size;
> + if (!*ENTRY_OCC(next_entry) || !*ENTRY_PSL(next_entry)) {
> + ctx->utilization--;
> + return 1;
> + }
> + FFSWAP(uint8_t, *ENTRY_OCC(entry), *ENTRY_OCC(next_entry));
> + memcpy(ENTRY_KEY(entry), ENTRY_KEY(next_entry), ctx->key_size);
> + memcpy(ENTRY_VAL(entry), ENTRY_VAL(next_entry), ctx->val_size);
These two memcpy can be combined (if one lays out key and val
sequentially in entry. Can even be combined with occ if you change the
entry layout as I outlined above.
> + *ENTRY_PSL(entry) = *ENTRY_PSL(next_entry) - 1;
> + entry = next_entry;
> + }
> + }
> + };
> + return 0;
> +}
> +
> +void av_hashtable_clear(AVHashtableContext* ctx)
> +{
> + memset(ctx->table, 0, ctx->entry_size * ctx->max_entries);
> +}
> +
> +void av_hashtable_destroy(AVHashtableContext* ctx)
> +{
> + av_freep(&ctx->table);
> + av_freep(&ctx->set_key);
> + av_freep(&ctx->set_val);
> + av_freep(&ctx->tmp_key);
> + av_freep(&ctx->tmp_val);
> +}
> \ No newline at end of file
> diff --git a/libavutil/hashtable.h b/libavutil/hashtable.h
> new file mode 100644
> index 0000000000..aac31ee922
> --- /dev/null
> +++ b/libavutil/hashtable.h
> @@ -0,0 +1,62 @@
> +/*
> + * Generic hashtable
> + * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg 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.
> + *
> + * FFmpeg 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 FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#ifndef AVUTIL_HASHTABLE_H
> +#define AVUTIL_HASHTABLE_H
> +
> +#include <stddef.h>
> +
> +#include "crc.h"
> +
> +/* Implements a hash table using Robin Hood open addressing.
> + * See: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
> + *
> + * Entry slots are layed out in memory as follows:
> + * - [1 byte] occupancy flag that indicates whether a slot if occupied.
> + * - [key_size bytes] entry key.
> + * - [val_size bytes] entry value.
> + * - [sizeof(size_t) bytes] PSL (probe sequence length), used by the Robin Hood
> + * algorithm.
Such things should not be made public. Even if
sizeof(AVHashtableContext) were part of the ABI.
> + */
> +
> +typedef struct AVHashtableContext {
> + size_t key_size;
> + size_t val_size;
> + size_t entry_size;
> + size_t max_entries;
> + size_t utilization;
> + const AVCRC *crc;
You don't need the complete type here, so by using struct AVCRC *crc you
can avoid the crc.h inclusion.
> + uint8_t *table;
> + /* used for swaps during insertion */
> + uint8_t *set_key;
> + uint8_t *set_val;
> + uint8_t *tmp_key;
> + uint8_t *tmp_val;
> +} AVHashtableContext;
In patch 2/2 you are using this in a way that makes
sizeof(AVHashtableContext) part of the ABI. Is this intended?
Even if it is, the user should be forbidden from accessing anything in it.
> +
> +int av_hashtable_init(AVHashtableContext* ctx, size_t key_size, size_t val_size, size_t max_entries);
We generally use
> +int av_hashtable_get(const AVHashtableContext* ctx, const void* key, void* val);
> +int av_hashtable_set(AVHashtableContext* ctx, const void* key, const void* val);
> +int av_hashtable_delete(AVHashtableContext* ctx, const void* key);
> +void av_hashtable_clear(AVHashtableContext* ctx);
> +void av_hashtable_destroy(AVHashtableContext* ctx);
> +
> +#endif
> \ No newline at end of file
> diff --git a/libavutil/tests/hashtable.c b/libavutil/tests/hashtable.c
> new file mode 100644
> index 0000000000..1cdbd7afd3
> --- /dev/null
> +++ b/libavutil/tests/hashtable.c
> @@ -0,0 +1,104 @@
> +/*
> + * Generic hashtable tests
> + * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg 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.
> + *
> + * FFmpeg 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 FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include "libavutil/avassert.h"
> +#include "libavutil/hashtable.h"
> +
> +int main(void)
> +{
> + AVHashtableContext ctx;
> + int k, v;
> +
> + // hashtable can store up to 3 int->int entries
> + av_assert0(!av_hashtable_init(&ctx, sizeof(int), sizeof(int), 3));
> +
> + // unsuccessful deletes return 0
> + k = 1;
> + av_assert0(!av_hashtable_delete(&ctx, &k));
> +
> + // unsuccessful gets return 0
> + k = 1;
> + av_assert0(!av_hashtable_get(&ctx, &k, &v));
> +
> + // successful sets returns 1
> + k = 1;
> + v = 1;
> + av_assert0(av_hashtable_set(&ctx, &k, &v));
> +
> + // get should now contain 1
> + k = 1;
> + v = 0;
> + av_assert0(av_hashtable_get(&ctx, &k, &v));
> + av_assert0(v == 1);
> +
> + // updating sets should return 1
> + k = 1;
> + v = 2;
> + av_assert0(av_hashtable_set(&ctx, &k, &v));
> +
> + // get should now contain 2
> + k = 1;
> + v = 0;
> + av_assert0(av_hashtable_get(&ctx, &k, &v));
> + av_assert0(v == 2);
> +
> + // fill the table
> + k = 2;
> + v = 2;
> + av_assert0(av_hashtable_set(&ctx, &k, &v));
> + k = 3;
> + v = 3;
> + av_assert0(av_hashtable_set(&ctx, &k, &v));
> +
> + // inserting sets on a full table should return 0
> + k = 4;
> + v = 4;
> + av_assert0(!av_hashtable_set(&ctx, &k, &v));
> +
> + // updating sets on a full table should return 1
> + k = 1;
> + v = 4;
> + av_assert0(av_hashtable_set(&ctx, &k, &v));
> + v = 0;
> + av_assert0(av_hashtable_get(&ctx, &k, &v));
> + av_assert0(v == 4);
> +
> + // successful deletes should return 1
> + k = 1;
> + av_assert0(av_hashtable_delete(&ctx, &k));
> +
> + // get should now return 0
> + av_assert0(!av_hashtable_get(&ctx, &k, &v));
> +
> + // sanity check remaining keys
> + k = 2;
> + v = 0;
> + av_assert0(av_hashtable_get(&ctx, &k, &v));
> + av_assert0(v == 2);
> + k = 3;
> + v = 0;
> + av_assert0(av_hashtable_get(&ctx, &k, &v));
> + av_assert0(v == 3);
> +
> + av_hashtable_destroy(&ctx);
> +
> + return 0;
> +}
> \ No newline at end of file
You should add these newlines, they are AFAIK required by the spec.
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
* [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table
@ 2024-02-05 5:27 Connor Worley
2024-02-05 12:00 ` Andreas Rheinhardt
0 siblings, 1 reply; 9+ messages in thread
From: Connor Worley @ 2024-02-05 5:27 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Connor Worley
Signed-off-by: Connor Worley <connorbworley@gmail.com>
---
libavutil/Makefile | 2 +
libavutil/hashtable.c | 172 ++++++++++++++++++++++++++++++++++++
libavutil/hashtable.h | 62 +++++++++++++
libavutil/tests/hashtable.c | 104 ++++++++++++++++++++++
4 files changed, 340 insertions(+)
create mode 100644 libavutil/hashtable.c
create mode 100644 libavutil/hashtable.h
create mode 100644 libavutil/tests/hashtable.c
diff --git a/libavutil/Makefile b/libavutil/Makefile
index e7709b97d0..be75d464fc 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -138,6 +138,7 @@ OBJS = adler32.o \
fixed_dsp.o \
frame.o \
hash.o \
+ hashtable.o \
hdr_dynamic_metadata.o \
hdr_dynamic_vivid_metadata.o \
hmac.o \
@@ -251,6 +252,7 @@ TESTPROGS = adler32 \
file \
fifo \
hash \
+ hashtable \
hmac \
hwdevice \
integer \
diff --git a/libavutil/hashtable.c b/libavutil/hashtable.c
new file mode 100644
index 0000000000..fb0f0aae99
--- /dev/null
+++ b/libavutil/hashtable.c
@@ -0,0 +1,172 @@
+/*
+ * Generic hashtable
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stdint.h>
+
+#include "error.h"
+#include "mem.h"
+#include "hashtable.h"
+#include "string.h"
+
+#define ENTRY_OCC(entry) (entry)
+#define ENTRY_KEY(entry) (ENTRY_OCC(entry) + 1)
+#define ENTRY_VAL(entry) (ENTRY_KEY(entry) + ctx->key_size)
+#define ENTRY_PSL(entry) (size_t*) (ENTRY_VAL(entry) + ctx->val_size)
+
+#define KEYS_EQUAL(k1, k2) !memcmp(k1, k2, ctx->key_size)
+
+int av_hashtable_init(AVHashtableContext* ctx, size_t key_size, size_t val_size, size_t max_entries)
+{
+ ctx->key_size = key_size;
+ ctx->val_size = val_size;
+ ctx->entry_size = 1 + key_size + val_size + sizeof(size_t);
+ ctx->max_entries = max_entries;
+ ctx->utilization = 0;
+ ctx->crc = av_crc_get_table(AV_CRC_32_IEEE);
+ if (!ctx->crc)
+ return AVERROR_BUG;
+ ctx->table = av_mallocz(ctx->entry_size * max_entries);
+ if (!ctx->table)
+ return AVERROR(ENOMEM);
+ ctx->set_key = av_malloc(key_size);
+ if (!ctx->set_key)
+ return AVERROR(ENOMEM);
+ ctx->set_val = av_malloc(key_size);
+ if (!ctx->set_val)
+ return AVERROR(ENOMEM);
+ ctx->tmp_key = av_malloc(key_size);
+ if (!ctx->tmp_key)
+ return AVERROR(ENOMEM);
+ ctx->tmp_val = av_malloc(val_size);
+ if (!ctx->tmp_val)
+ return AVERROR(ENOMEM);
+ return 0;
+}
+
+static size_t hash_key(const AVHashtableContext* ctx, const void* key)
+{
+ return av_crc(ctx->crc, 0, key, ctx->key_size) % ctx->max_entries;
+}
+
+int av_hashtable_get(const AVHashtableContext* ctx, const void* key, void* val)
+{
+ size_t hash = hash_key(ctx, key);
+
+ if (!ctx->utilization)
+ return 0;
+
+ for (size_t psl = 0; psl < ctx->max_entries; psl++) {
+ size_t wrapped_index = (hash + psl) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || *ENTRY_PSL(entry) < psl)
+ return 0;
+ if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
+ memcpy(val, ENTRY_VAL(entry), ctx->val_size);
+ return 1;
+ }
+ }
+ return 0;
+}
+
+int av_hashtable_set(AVHashtableContext* ctx, const void* key, const void* val)
+{
+ int swapping = 0;
+ size_t psl = 0;
+ size_t hash = hash_key(ctx, key);
+
+ memcpy(ctx->set_key, key, ctx->key_size);
+ memcpy(ctx->set_val, val, ctx->val_size);
+
+ for (size_t i = 0; i < ctx->max_entries; i++) {
+ size_t wrapped_index = (hash + i) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || (!swapping && KEYS_EQUAL(ENTRY_KEY(entry), ctx->set_key))) {
+ if (!*ENTRY_OCC(entry))
+ ctx->utilization++;
+ *ENTRY_OCC(entry) = 1;
+ memcpy(ENTRY_KEY(entry), ctx->set_key, ctx->key_size);
+ memcpy(ENTRY_VAL(entry), ctx->set_val, ctx->val_size);
+ *ENTRY_PSL(entry) = psl;
+ return 1;
+ }
+ if (*ENTRY_PSL(entry) < psl) {
+ if (ctx->utilization == ctx->max_entries)
+ return 0;
+ swapping = 1;
+ memcpy(ctx->tmp_key, ctx->set_key, ctx->key_size);
+ memcpy(ctx->tmp_val, ctx->set_val, ctx->val_size);
+ memcpy(ctx->set_key, ENTRY_KEY(entry), ctx->key_size);
+ memcpy(ctx->set_val, ENTRY_VAL(entry), ctx->val_size);
+ memcpy(ENTRY_KEY(entry), ctx->tmp_key, ctx->key_size);
+ memcpy(ENTRY_VAL(entry), ctx->tmp_val, ctx->val_size);
+ FFSWAP(size_t, psl, *ENTRY_PSL(entry));
+ }
+ psl++;
+ }
+ return 0;
+}
+
+int av_hashtable_delete(AVHashtableContext* ctx, const void* key)
+{
+ uint8_t *next_entry;
+ size_t hash = hash_key(ctx, key);
+
+ if (!ctx->utilization)
+ return 0;
+
+ for (size_t psl = 0; psl < ctx->max_entries; psl++) {
+ size_t wrapped_index = (hash + psl) % ctx->max_entries;
+ uint8_t *entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(entry) || *ENTRY_PSL(entry) < psl)
+ return 0;
+ if (KEYS_EQUAL(ENTRY_KEY(entry), key)) {
+ *ENTRY_OCC(entry) = 0;
+ for (psl++; psl < ctx->max_entries; psl++) {
+ wrapped_index = (hash + psl) % ctx->max_entries;
+ next_entry = ctx->table + wrapped_index * ctx->entry_size;
+ if (!*ENTRY_OCC(next_entry) || !*ENTRY_PSL(next_entry)) {
+ ctx->utilization--;
+ return 1;
+ }
+ FFSWAP(uint8_t, *ENTRY_OCC(entry), *ENTRY_OCC(next_entry));
+ memcpy(ENTRY_KEY(entry), ENTRY_KEY(next_entry), ctx->key_size);
+ memcpy(ENTRY_VAL(entry), ENTRY_VAL(next_entry), ctx->val_size);
+ *ENTRY_PSL(entry) = *ENTRY_PSL(next_entry) - 1;
+ entry = next_entry;
+ }
+ }
+ };
+ return 0;
+}
+
+void av_hashtable_clear(AVHashtableContext* ctx)
+{
+ memset(ctx->table, 0, ctx->entry_size * ctx->max_entries);
+}
+
+void av_hashtable_destroy(AVHashtableContext* ctx)
+{
+ av_freep(&ctx->table);
+ av_freep(&ctx->set_key);
+ av_freep(&ctx->set_val);
+ av_freep(&ctx->tmp_key);
+ av_freep(&ctx->tmp_val);
+}
\ No newline at end of file
diff --git a/libavutil/hashtable.h b/libavutil/hashtable.h
new file mode 100644
index 0000000000..aac31ee922
--- /dev/null
+++ b/libavutil/hashtable.h
@@ -0,0 +1,62 @@
+/*
+ * Generic hashtable
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_HASHTABLE_H
+#define AVUTIL_HASHTABLE_H
+
+#include <stddef.h>
+
+#include "crc.h"
+
+/* Implements a hash table using Robin Hood open addressing.
+ * See: https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf
+ *
+ * Entry slots are layed out in memory as follows:
+ * - [1 byte] occupancy flag that indicates whether a slot if occupied.
+ * - [key_size bytes] entry key.
+ * - [val_size bytes] entry value.
+ * - [sizeof(size_t) bytes] PSL (probe sequence length), used by the Robin Hood
+ * algorithm.
+ */
+
+typedef struct AVHashtableContext {
+ size_t key_size;
+ size_t val_size;
+ size_t entry_size;
+ size_t max_entries;
+ size_t utilization;
+ const AVCRC *crc;
+ uint8_t *table;
+ /* used for swaps during insertion */
+ uint8_t *set_key;
+ uint8_t *set_val;
+ uint8_t *tmp_key;
+ uint8_t *tmp_val;
+} AVHashtableContext;
+
+int av_hashtable_init(AVHashtableContext* ctx, size_t key_size, size_t val_size, size_t max_entries);
+int av_hashtable_get(const AVHashtableContext* ctx, const void* key, void* val);
+int av_hashtable_set(AVHashtableContext* ctx, const void* key, const void* val);
+int av_hashtable_delete(AVHashtableContext* ctx, const void* key);
+void av_hashtable_clear(AVHashtableContext* ctx);
+void av_hashtable_destroy(AVHashtableContext* ctx);
+
+#endif
\ No newline at end of file
diff --git a/libavutil/tests/hashtable.c b/libavutil/tests/hashtable.c
new file mode 100644
index 0000000000..1cdbd7afd3
--- /dev/null
+++ b/libavutil/tests/hashtable.c
@@ -0,0 +1,104 @@
+/*
+ * Generic hashtable tests
+ * Copyright (C) 2024 Connor Worley <connorbworley@gmail.com>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg 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.
+ *
+ * FFmpeg 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 FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "libavutil/avassert.h"
+#include "libavutil/hashtable.h"
+
+int main(void)
+{
+ AVHashtableContext ctx;
+ int k, v;
+
+ // hashtable can store up to 3 int->int entries
+ av_assert0(!av_hashtable_init(&ctx, sizeof(int), sizeof(int), 3));
+
+ // unsuccessful deletes return 0
+ k = 1;
+ av_assert0(!av_hashtable_delete(&ctx, &k));
+
+ // unsuccessful gets return 0
+ k = 1;
+ av_assert0(!av_hashtable_get(&ctx, &k, &v));
+
+ // successful sets returns 1
+ k = 1;
+ v = 1;
+ av_assert0(av_hashtable_set(&ctx, &k, &v));
+
+ // get should now contain 1
+ k = 1;
+ v = 0;
+ av_assert0(av_hashtable_get(&ctx, &k, &v));
+ av_assert0(v == 1);
+
+ // updating sets should return 1
+ k = 1;
+ v = 2;
+ av_assert0(av_hashtable_set(&ctx, &k, &v));
+
+ // get should now contain 2
+ k = 1;
+ v = 0;
+ av_assert0(av_hashtable_get(&ctx, &k, &v));
+ av_assert0(v == 2);
+
+ // fill the table
+ k = 2;
+ v = 2;
+ av_assert0(av_hashtable_set(&ctx, &k, &v));
+ k = 3;
+ v = 3;
+ av_assert0(av_hashtable_set(&ctx, &k, &v));
+
+ // inserting sets on a full table should return 0
+ k = 4;
+ v = 4;
+ av_assert0(!av_hashtable_set(&ctx, &k, &v));
+
+ // updating sets on a full table should return 1
+ k = 1;
+ v = 4;
+ av_assert0(av_hashtable_set(&ctx, &k, &v));
+ v = 0;
+ av_assert0(av_hashtable_get(&ctx, &k, &v));
+ av_assert0(v == 4);
+
+ // successful deletes should return 1
+ k = 1;
+ av_assert0(av_hashtable_delete(&ctx, &k));
+
+ // get should now return 0
+ av_assert0(!av_hashtable_get(&ctx, &k, &v));
+
+ // sanity check remaining keys
+ k = 2;
+ v = 0;
+ av_assert0(av_hashtable_get(&ctx, &k, &v));
+ av_assert0(v == 2);
+ k = 3;
+ v = 0;
+ av_assert0(av_hashtable_get(&ctx, &k, &v));
+ av_assert0(v == 3);
+
+ av_hashtable_destroy(&ctx);
+
+ return 0;
+}
\ No newline at end of file
--
2.40.1
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2025-04-20 15:20 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-04-20 13:08 [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Emma Worley
2025-04-20 13:08 ` [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable and improve Resolume compatibility Emma Worley
2025-04-20 15:10 ` Nicolas George
2025-04-20 15:15 ` James Almer
2025-04-20 15:20 ` [FFmpeg-devel] [PATCH 1/2] lavu/hashtable: create generic robin hood hash table Nicolas George
-- strict thread matches above, loose matches on Subject: below --
2024-02-05 5:27 Connor Worley
2024-02-05 12:00 ` Andreas Rheinhardt
2024-02-06 5:00 ` Connor Worley
2024-02-06 10:13 ` Connor Worley
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
This inbox may be cloned and mirrored by anyone:
git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \
ffmpegdev@gitmailbox.com
public-inbox-index ffmpegdev
Example config snippet for mirrors.
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git