Merge branch 'potatosalad/erts/binary_find_bif_improved/PR-1480/OTP-14610'

* potatosalad/erts/binary_find_bif_improved/PR-1480/OTP-14610:
  stdlib: Improved BIF for binary matches and split.

2 files changed, 602 insertions, 507 deletions

diff --git a/erts/emulator/beam/erl_alloc.types b/erts/emulator/beam/erl_alloc.types
index 8142ea8893..11884299e2 100644
--- a/erts/emulator/beam/erl_alloc.types
+++ b/erts/emulator/beam/erl_alloc.types
@@ -258,6 +258,7 @@ type    MREF_ENT	STANDARD	SYSTEM		magic_ref_entry
 type	MREF_TAB_BKTS	STANDARD	SYSTEM		magic_ref_table_buckets
 type	MREF_TAB	LONG_LIVED	SYSTEM		magic_ref_table
 type	MINDIRECTION	FIXED_SIZE	SYSTEM		magic_indirection
+type	BINARY_FIND	SHORT_LIVED	PROCESSES	binary_find
 
 type	THR_Q_EL	STANDARD   	SYSTEM		thr_q_element
 type	THR_Q_EL_SL	FIXED_SIZE	SYSTEM		sl_thr_q_element
diff --git a/erts/emulator/beam/erl_bif_binary.c b/erts/emulator/beam/erl_bif_binary.c
index dcffde5777..4cafa499a9 100644
--- a/erts/emulator/beam/erl_bif_binary.c
+++ b/erts/emulator/beam/erl_bif_binary.c
@@ -171,6 +171,16 @@ static void *my_alloc(MyAllocator *my, Uint size)
 
 #define ALPHABET_SIZE 256
 
+typedef struct _findall_data {
+    Uint pos;
+    Uint len;
+#ifdef HARDDEBUG
+    Uint id;
+#endif
+    Eterm epos;
+    Eterm elen;
+} FindallData;
+
 typedef struct _ac_node {
 #ifdef HARDDEBUG
     Uint32 id;                        /* To identify h pointer targets when
@@ -208,6 +218,103 @@ typedef struct _bm_data {
     Sint badshift[ALPHABET_SIZE];
 } BMData;
 
+typedef struct _ac_find_all_state {
+    ACNode *q;
+    Uint pos;
+    Uint len;
+    Uint m;
+    Uint allocated;
+    FindallData *out;
+} ACFindAllState;
+
+typedef struct _ac_find_first_state {
+    ACNode *q;
+    Uint pos;
+    Uint len;
+    ACNode *candidate;
+    Uint candidate_start;
+} ACFindFirstState;
+
+typedef struct _bm_find_all_state {
+    Sint pos;
+    Sint len;
+    Uint m;
+    Uint allocated;
+    FindallData *out;
+} BMFindAllState;
+
+typedef struct _bm_find_first_state {
+    Sint pos;
+    Sint len;
+} BMFindFirstState;
+
+typedef enum _bf_return {
+    BF_RESTART = -3,
+    BF_NOT_FOUND,
+    BF_BADARG,
+    BF_OK
+} BFReturn;
+
+typedef struct _binary_find_all_context {
+    ErtsHeapFactory factory;
+    Eterm term;
+    Sint head;
+    Sint tail;
+    Uint end_pos;
+    Uint size;
+    FindallData *data;
+    union {
+	ACFindAllState ac;
+	BMFindAllState bm;
+    } d;
+} BinaryFindAllContext;
+
+typedef struct _binary_find_first_context {
+    Uint pos;
+    Uint len;
+    union {
+	ACFindFirstState ac;
+	BMFindFirstState bm;
+    } d;
+} BinaryFindFirstContext;
+
+typedef struct _binary_find_context BinaryFindContext;
+
+typedef struct _binary_find_search {
+    void (*init) (BinaryFindContext *);
+    BFReturn (*find) (BinaryFindContext *, byte *);
+    void (*done) (BinaryFindContext *);
+} BinaryFindSearch;
+
+typedef Eterm (*BinaryFindResult)(Process *, Eterm, BinaryFindContext **);
+
+typedef enum _binary_find_state {
+    BFSearch,
+    BFResult,
+    BFDone
+} BinaryFindState;
+
+struct _binary_find_context {
+    Eterm pat_type;
+    Eterm pat_term;
+    Binary *pat_bin;
+    Uint flags;
+    Uint hsstart;
+    Uint hsend;
+    int loop_factor;
+    int exported;
+    Uint reds;
+    BinaryFindState state;
+    Eterm trap_term;
+    BinaryFindSearch *search;
+    BinaryFindResult not_found;
+    BinaryFindResult found;
+    union {
+	BinaryFindAllContext fa;
+	BinaryFindFirstContext ff;
+    } u;
+};
+
 #ifdef HARDDEBUG
 static void dump_bm_data(BMData *bm);
 static void dump_ac_trie(ACTrie *act);
@@ -414,32 +521,25 @@ static void ac_compute_failure_functions(ACTrie *act, ACNode **qbuff)
  * Basic AC finds the first end before the first start...
  *
  */
-typedef struct {
-    ACNode *q;
-    Uint pos;
-    Uint len;
-    ACNode *candidate;
-    Uint candidate_start;
-} ACFindFirstState;
-
-
-static void ac_init_find_first_match(ACFindFirstState *state, ACTrie *act, Sint startpos, Uint len)
+static void ac_init_find_first_match(BinaryFindContext *ctx)
 {
+    ACFindFirstState *state = &(ctx->u.ff.d.ac);
+    ACTrie *act = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
     state->q = act->root;
-    state->pos = startpos;
-    state->len = len;
+    state->pos = ctx->hsstart;
+    state->len = ctx->hsend;
     state->candidate = NULL;
     state->candidate_start = 0;
 }
-#define AC_OK 0
-#define AC_NOT_FOUND -1
-#define AC_RESTART -2
 
 #define AC_LOOP_FACTOR 10
 
-static int ac_find_first_match(ACFindFirstState *state, byte *haystack,
-				Uint *mpos, Uint *mlen, Uint *reductions)
+static BFReturn ac_find_first_match(BinaryFindContext *ctx, byte *haystack)
 {
+    ACFindFirstState *state = &(ctx->u.ff.d.ac);
+    Uint *mpos = &(ctx->u.ff.pos);
+    Uint *mlen = &(ctx->u.ff.len);
+    Uint *reductions = &(ctx->reds);
     ACNode *q = state->q;
     Uint i = state->pos;
     ACNode *candidate = state->candidate, *r;
@@ -455,7 +555,7 @@ static int ac_find_first_match(ACFindFirstState *state, byte *haystack,
 	    state->len = len;
 	    state->candidate = candidate;
 	    state->candidate_start = candidate_start;
-	    return AC_RESTART;
+	    return BF_RESTART;
 	}
 
 	while (q->g[haystack[i]] == NULL && q->h != q) {
@@ -485,68 +585,33 @@ static int ac_find_first_match(ACFindFirstState *state, byte *haystack,
     }
     *reductions = reds;
     if (!candidate) {
-	return AC_NOT_FOUND;
+	return BF_NOT_FOUND;
     }
 #ifdef HARDDEBUG
     dump_ac_node(candidate,0,'?');
 #endif
     *mpos = candidate_start;
     *mlen = candidate->d;
-    return AC_OK;
+    return BF_OK;
 }
 
-typedef struct _findall_data {
-    Uint pos;
-    Uint len;
-#ifdef HARDDEBUG
-    Uint id;
-#endif
-    Eterm epos;
-    Eterm elen;
-} FindallData;
-
-typedef struct {
-    ACNode *q;
-    Uint pos;
-    Uint len;
-    Uint m;
-    Uint allocated;
-    FindallData *out;
-} ACFindAllState;
-
-static void ac_init_find_all(ACFindAllState *state, ACTrie *act, Sint startpos, Uint len)
+static void ac_init_find_all(BinaryFindContext *ctx)
 {
+    ACFindAllState *state = &(ctx->u.fa.d.ac);
+    ACTrie *act = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
     state->q = act->root;
-    state->pos = startpos;
-    state->len = len;
+    state->pos = ctx->hsstart;
+    state->len = ctx->hsend;
     state->m = 0;
     state->allocated = 0;
     state->out = NULL;
 }
 
-static void ac_restore_find_all(ACFindAllState *state,
-                                const ACFindAllState *src)
-{
-    memcpy(state, src, sizeof(ACFindAllState));
-    if (state->allocated > 0) {
-	state->out = erts_alloc(ERTS_ALC_T_TMP, sizeof(FindallData) * (state->allocated));
-	memcpy(state->out, src+1, sizeof(FindallData)*state->m);
-    } else {
-	state->out = NULL;
-    }
-}
-
-static void ac_serialize_find_all(const ACFindAllState *state,
-                                  ACFindAllState *dst)
-{
-    memcpy(dst, state, sizeof(ACFindAllState));
-    memcpy(dst+1, state->out, sizeof(FindallData)*state->m);
-}
-
-static void ac_clean_find_all(ACFindAllState *state)
+static void ac_clean_find_all(BinaryFindContext *ctx)
 {
+    ACFindAllState *state = &(ctx->u.fa.d.ac);
     if (state->out != NULL) {
-	erts_free(ERTS_ALC_T_TMP, state->out);
+	erts_free(ERTS_ALC_T_BINARY_FIND, state->out);
     }
 #ifdef HARDDEBUG
     state->out = NULL;
@@ -558,9 +623,10 @@ static void ac_clean_find_all(ACFindAllState *state)
  * Differs to the find_first function in that it stores all matches and the values
  * arte returned only in the state.
  */
-static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack,
-				       Uint *reductions)
+static BFReturn ac_find_all_non_overlapping(BinaryFindContext *ctx, byte *haystack)
 {
+    ACFindAllState *state = &(ctx->u.fa.d.ac);
+    Uint *reductions = &(ctx->reds);
     ACNode *q = state->q;
     Uint i = state->pos;
     Uint rstart;
@@ -571,7 +637,6 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack,
     FindallData *out = state->out;
     register Uint reds = *reductions;
 
-
     while (i < len) {
 	if (--reds == 0) {
 	    state->q = q;
@@ -580,7 +645,7 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack,
 	    state->m = m;
 	    state->allocated = allocated;
 	    state->out = out;
-	    return AC_RESTART;
+	    return BF_RESTART;
 	}
 	while (q->g[haystack[i]] == NULL && q->h != q) {
 	    q = q->h;
@@ -618,11 +683,11 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack,
 		    if (m >= allocated) {
 			if (!allocated) {
 			    allocated = 10;
-			    out = erts_alloc(ERTS_ALC_T_TMP,
+			    out = erts_alloc(ERTS_ALC_T_BINARY_FIND,
 					     sizeof(FindallData) * allocated);
 			} else {
 			    allocated *= 2;
-			    out = erts_realloc(ERTS_ALC_T_TMP, out,
+			    out = erts_realloc(ERTS_ALC_T_BINARY_FIND, out,
 					       sizeof(FindallData) *
 					       allocated);
 			}
@@ -649,7 +714,7 @@ static int ac_find_all_non_overlapping(ACFindAllState *state, byte *haystack,
     *reductions = reds;
     state->m = m;
     state->out = out;
-    return (m == 0) ? AC_NOT_FOUND : AC_OK;
+    return (m == 0) ? BF_NOT_FOUND : BF_OK;
 }
 
 /*
@@ -736,27 +801,22 @@ static void compute_goodshifts(BMData *bmd)
     erts_free(ERTS_ALC_T_TMP, suffixes);
 }
 
-typedef struct {
-    Sint pos;
-    Sint len;
-} BMFindFirstState;
-
-#define BM_OK 0 /* used only for find_all */
-#define BM_NOT_FOUND -1
-#define BM_RESTART -2
 #define BM_LOOP_FACTOR 10 /* Should we have a higher value? */
 
-static void bm_init_find_first_match(BMFindFirstState *state, Sint startpos,
-				     Uint len)
+static void bm_init_find_first_match(BinaryFindContext *ctx)
 {
-    state->pos = startpos;
-    state->len = (Sint) len;
+    BMFindFirstState *state = &(ctx->u.ff.d.bm);
+    state->pos = ctx->hsstart;
+    state->len = ctx->hsend;
 }
 
-
-static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd,
-				byte *haystack, Uint *reductions)
+static BFReturn bm_find_first_match(BinaryFindContext *ctx, byte *haystack)
 {
+    BMFindFirstState *state = &(ctx->u.ff.d.bm);
+    BMData *bmd = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
+    Uint *mpos = &(ctx->u.ff.pos);
+    Uint *mlen = &(ctx->u.ff.len);
+    Uint *reductions = &(ctx->reds);
     Sint blen = bmd->len;
     Sint len = state->len;
     Sint *gs = bmd->goodshift;
@@ -769,61 +829,37 @@ static Sint bm_find_first_match(BMFindFirstState *state, BMData *bmd,
     while (j <= len - blen) {
 	if (--reds == 0) {
 	    state->pos = j;
-	    return BM_RESTART;
+	    return BF_RESTART;
 	}
 	for (i = blen - 1; i >= 0 && needle[i] == haystack[i + j]; --i)
 	    ;
 	if (i < 0) { /* found */
 	    *reductions = reds;
-	    return j;
+	    *mpos = (Uint) j;
+	    *mlen = (Uint) blen;
+	    return BF_OK;
 	}
 	j += MAX(gs[i],bs[haystack[i+j]] - blen + 1 + i);
     }
     *reductions = reds;
-    return BM_NOT_FOUND;
+    return BF_NOT_FOUND;
 }
 
-typedef struct {
-    Sint pos;
-    Sint len;
-    Uint m;
-    Uint allocated;
-    FindallData *out;
-} BMFindAllState;
-
-static void bm_init_find_all(BMFindAllState *state, Sint startpos, Uint len)
+static void bm_init_find_all(BinaryFindContext *ctx)
 {
-    state->pos = startpos;
-    state->len = (Sint) len;
+    BMFindAllState *state = &(ctx->u.fa.d.bm);
+    state->pos = ctx->hsstart;
+    state->len = ctx->hsend;
     state->m = 0;
     state->allocated = 0;
     state->out = NULL;
 }
 
-static void bm_restore_find_all(BMFindAllState *state,
-                                const BMFindAllState *src)
-{
-    memcpy(state, src, sizeof(BMFindAllState));
-    if (state->allocated > 0) {
-	state->out = erts_alloc(ERTS_ALC_T_TMP, sizeof(FindallData) *
-				(state->allocated));
-	memcpy(state->out, src+1, sizeof(FindallData)*state->m);
-    } else {
-	state->out = NULL;
-    }
-}
-
-static void bm_serialize_find_all(const BMFindAllState *state,
-                                  BMFindAllState *dst)
-{
-    memcpy(dst, state, sizeof(BMFindAllState));
-    memcpy(dst+1, state->out, sizeof(FindallData)*state->m);
-}
-
-static void bm_clean_find_all(BMFindAllState *state)
+static void bm_clean_find_all(BinaryFindContext *ctx)
 {
+    BMFindAllState *state = &(ctx->u.fa.d.bm);
     if (state->out != NULL) {
-	erts_free(ERTS_ALC_T_TMP, state->out);
+	erts_free(ERTS_ALC_T_BINARY_FIND, state->out);
     }
 #ifdef HARDDEBUG
     state->out = NULL;
@@ -835,10 +871,11 @@ static void bm_clean_find_all(BMFindAllState *state)
  * Differs to the find_first function in that it stores all matches and the
  * values are returned only in the state.
  */
-static Sint bm_find_all_non_overlapping(BMFindAllState *state,
-					BMData *bmd, byte *haystack,
-					Uint *reductions)
+static BFReturn bm_find_all_non_overlapping(BinaryFindContext *ctx, byte *haystack)
 {
+    BMFindAllState *state = &(ctx->u.fa.d.bm);
+    BMData *bmd = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
+    Uint *reductions = &(ctx->reds);
     Sint blen = bmd->len;
     Sint len = state->len;
     Sint *gs = bmd->goodshift;
@@ -857,7 +894,7 @@ static Sint bm_find_all_non_overlapping(BMFindAllState *state,
 	    state->m = m;
 	    state->allocated = allocated;
 	    state->out = out;
-	    return BM_RESTART;
+	    return BF_RESTART;
 	}
 	for (i = blen - 1; i >= 0 && needle[i] == haystack[i + j]; --i)
 	    ;
@@ -865,10 +902,11 @@ static Sint bm_find_all_non_overlapping(BMFindAllState *state,
 	    if (m >= allocated) {
 		if (!allocated) {
 		    allocated = 10;
-		    out = erts_alloc(ERTS_ALC_T_TMP, sizeof(FindallData) * allocated);
+		    out = erts_alloc(ERTS_ALC_T_BINARY_FIND,
+				     sizeof(FindallData) * allocated);
 		} else {
 		    allocated *= 2;
-		    out = erts_realloc(ERTS_ALC_T_TMP, out,
+		    out = erts_realloc(ERTS_ALC_T_BINARY_FIND, out,
 				       sizeof(FindallData) * allocated);
 		}
 	    }
@@ -883,7 +921,7 @@ static Sint bm_find_all_non_overlapping(BMFindAllState *state,
     state->m = m;
     state->out = out;
     *reductions = reds;
-    return (m == 0) ? BM_NOT_FOUND : BM_OK;
+    return (m == 0) ? BF_NOT_FOUND : BF_OK;
 }
 
 /*
@@ -1009,51 +1047,160 @@ BIF_RETTYPE binary_compile_pattern_1(BIF_ALIST_1)
     BIF_RET(ret);
 }
 
-#define DO_BIN_MATCH_OK 0
-#define DO_BIN_MATCH_BADARG -1
-#define DO_BIN_MATCH_RESTART -2
+#define BF_FLAG_GLOBAL		0x01
+#define BF_FLAG_SPLIT_TRIM	0x02
+#define BF_FLAG_SPLIT_TRIM_ALL	0x04
 
-#define BINARY_FIND_ALL		0x01
-#define BINARY_SPLIT_TRIM	0x02
-#define BINARY_SPLIT_TRIM_ALL	0x04
+static void bf_context_init(BinaryFindContext *ctx, BinaryFindResult not_found,
+			    BinaryFindResult single, BinaryFindResult global,
+			    Binary *pat_bin);
+static BinaryFindContext *bf_context_export(Process *p, BinaryFindContext *src);
+static int bf_context_destructor(Binary *ctx_bin);
+#ifdef HARDDEBUG
+static void bf_context_dump(BinaryFindContext *ctx);
+#endif
 
-typedef struct BinaryFindState {
-    Eterm type;
-    Uint  flags;
-    Uint  hsstart;
-    Uint  hsend;
-    Eterm (*not_found_result) (Process *, Eterm, struct BinaryFindState *);
-    Eterm (*single_result)    (Process *, Eterm, struct BinaryFindState *, Sint, Sint);
-    Eterm (*global_result)    (Process *, Eterm, struct BinaryFindState *, FindallData *, Uint);
-} BinaryFindState;
+static BinaryFindSearch bf_search_ac_global = {
+    ac_init_find_all,
+    ac_find_all_non_overlapping,
+    ac_clean_find_all
+};
+
+static BinaryFindSearch bf_search_ac_single = {
+    ac_init_find_first_match,
+    ac_find_first_match,
+    NULL
+};
+
+static BinaryFindSearch bf_search_bm_global = {
+    bm_init_find_all,
+    bm_find_all_non_overlapping,
+    bm_clean_find_all
+};
+
+static BinaryFindSearch bf_search_bm_single = {
+    bm_init_find_first_match,
+    bm_find_first_match,
+    NULL
+};
+
+static void bf_context_init(BinaryFindContext *ctx, BinaryFindResult not_found,
+			    BinaryFindResult single, BinaryFindResult global,
+			    Binary *pat_bin)
+{
+    ctx->exported = 0;
+    ctx->state = BFSearch;
+    ctx->not_found = not_found;
+    if (ctx->flags & BF_FLAG_GLOBAL) {
+	ctx->found = global;
+	if (ctx->pat_type == am_bm) {
+	    ctx->search = &bf_search_bm_global;
+	    ctx->loop_factor = BM_LOOP_FACTOR;
+	} else if (ctx->pat_type == am_ac) {
+	    ctx->search = &bf_search_ac_global;
+	    ctx->loop_factor = AC_LOOP_FACTOR;
+	}
+    } else {
+	ctx->found = single;
+	if (ctx->pat_type == am_bm) {
+	    ctx->search = &bf_search_bm_single;
+	    ctx->loop_factor = BM_LOOP_FACTOR;
+	} else if (ctx->pat_type == am_ac) {
+	    ctx->search = &bf_search_ac_single;
+	    ctx->loop_factor = AC_LOOP_FACTOR;
+	}
+    }
+    ctx->trap_term = THE_NON_VALUE;
+    ctx->pat_bin = pat_bin;
+    ctx->search->init(ctx);
+}
 
-typedef struct BinaryFindState_bignum {
-    Eterm           bignum_hdr;
-    BinaryFindState bfs;
-    union {
-	BMFindFirstState bmffs;
-	BMFindAllState   bmfas;
-	ACFindFirstState acffs;
-	ACFindAllState   acfas;
-    } data;
-} BinaryFindState_bignum;
-
-#define SIZEOF_BINARY_FIND_STATE(S) \
-	  (sizeof(BinaryFindState)+sizeof(S))
-
-#define SIZEOF_BINARY_FIND_ALL_STATE(S) \
-	  (sizeof(BinaryFindState)+sizeof(S)+(sizeof(FindallData)*(S).m))
-
-static Eterm do_match_not_found_result(Process *p, Eterm subject, BinaryFindState *bfs);
-static Eterm do_match_single_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    Sint pos, Sint len);
-static Eterm do_match_global_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    FindallData *fad, Uint fad_sz);
-static Eterm do_split_not_found_result(Process *p, Eterm subject, BinaryFindState *bfs);
-static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    Sint pos, Sint len);
-static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    FindallData *fad, Uint fad_sz);
+static BinaryFindContext *bf_context_export(Process *p, BinaryFindContext *src)
+{
+    Binary *ctx_bin;
+    BinaryFindContext *ctx;
+    Eterm *hp;
+
+    ASSERT(src->exported == 0);
+    ctx_bin = erts_create_magic_binary(sizeof(BinaryFindContext),
+				       bf_context_destructor);
+    ctx = ERTS_MAGIC_BIN_DATA(ctx_bin);
+    sys_memcpy(ctx, src, sizeof(BinaryFindContext));
+    if (ctx->pat_bin != NULL && ctx->pat_term == THE_NON_VALUE) {
+	hp = HAlloc(p, ERTS_MAGIC_REF_THING_SIZE * 2);
+	ctx->pat_term = erts_mk_magic_ref(&hp, &MSO(p), ctx->pat_bin);
+    } else {
+	hp = HAlloc(p, ERTS_MAGIC_REF_THING_SIZE);
+    }
+    ctx->trap_term = erts_mk_magic_ref(&hp, &MSO(p), ctx_bin);
+    ctx->exported = 1;
+    return ctx;
+}
+
+static int bf_context_destructor(Binary *ctx_bin)
+{
+    BinaryFindContext *ctx;
+
+    ctx = ERTS_MAGIC_BIN_DATA(ctx_bin);
+    if (ctx->state != BFDone) {
+	if (ctx->search->done != NULL) {
+	    ctx->search->done(ctx);
+	}
+	ctx->state = BFDone;
+    }
+    return 1;
+}
+
+#ifdef HARDDEBUG
+static void bf_context_dump(BinaryFindContext *ctx)
+{
+    if (ctx->pat_type == am_bm) {
+	BMData *bm;
+	bm = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
+	dump_bm_data(bm);
+    } else {
+	ACTrie *act;
+	act = ERTS_MAGIC_BIN_DATA(ctx->pat_bin);
+	dump_ac_trie(act);
+    }
+}
+#endif
+
+static Eterm do_match_not_found_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+static Eterm do_match_single_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+static Eterm do_match_global_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+static Eterm do_split_not_found_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindContext **ctxp);
+
+static BFReturn maybe_binary_match_compile(BinaryFindContext *ctx, Eterm arg, Binary **pat_bin)
+{
+    Eterm *tp;
+    ctx->pat_term = THE_NON_VALUE;
+    if (is_tuple(arg)) {
+	tp = tuple_val(arg);
+	if (arityval(*tp) != 2 || is_not_atom(tp[1])) {
+	    return BF_BADARG;
+	}
+	if (((tp[1] != am_bm) && (tp[1] != am_ac)) ||
+	    !is_internal_magic_ref(tp[2])) {
+	    return BF_BADARG;
+	}
+	*pat_bin = erts_magic_ref2bin(tp[2]);
+	if ((tp[1] == am_bm &&
+	     ERTS_MAGIC_BIN_DESTRUCTOR(*pat_bin) != cleanup_my_data_bm) ||
+	    (tp[1] == am_ac &&
+	     ERTS_MAGIC_BIN_DESTRUCTOR(*pat_bin) != cleanup_my_data_ac)) {
+	    *pat_bin = NULL;
+	    return BF_BADARG;
+	}
+	ctx->pat_type = tp[1];
+	ctx->pat_term = tp[2];
+    } else if (do_binary_match_compile(arg, &(ctx->pat_type), pat_bin) != 0) {
+	return BF_BADARG;
+    }
+    return BF_OK;
+}
 
 static int parse_match_opts_list(Eterm l, Eterm bin, Uint *posp, Uint *endp)
 {
@@ -1134,17 +1281,17 @@ static int parse_split_opts_list(Eterm l, Eterm bin, Uint *posp, Uint *endp, Uin
 	    Uint orig_size;
 	    if (is_atom(t)) {
 		if (t == am_global) {
-		    *optp |= BINARY_FIND_ALL;
+		    *optp |= BF_FLAG_GLOBAL;
 		    l = CDR(list_val(l));
 		    continue;
 		}
 		if (t == am_trim) {
-		    *optp |= BINARY_SPLIT_TRIM;
+		    *optp |= BF_FLAG_SPLIT_TRIM;
 		    l = CDR(list_val(l));
 		    continue;
 		}
 		if (t == am_trim_all) {
-		    *optp |= BINARY_SPLIT_TRIM_ALL;
+		    *optp |= BF_FLAG_SPLIT_TRIM_ALL;
 		    l = CDR(list_val(l));
 		    continue;
 		}
@@ -1197,266 +1344,160 @@ static int parse_split_opts_list(Eterm l, Eterm bin, Uint *posp, Uint *endp, Uin
     }
 }
 
-static int do_binary_find(Process *p, Eterm subject, BinaryFindState *bfs, Binary *bin,
-			  Eterm state_term, Eterm *res_term)
+static BFReturn do_binary_find(Process *p, Eterm subject, BinaryFindContext **ctxp,
+			       Binary *pat_bin, Binary *ctx_bin, Eterm *res_term)
 {
-    byte *bytes;
-    Uint bitoffs, bitsize;
-    byte *temp_alloc = NULL;
-    BinaryFindState_bignum *state_ptr = NULL;
+    BinaryFindContext *ctx;
+    int is_first_call;
+    Uint initial_reds;
+    BFReturn runres;
 
-    ERTS_GET_BINARY_BYTES(subject, bytes, bitoffs, bitsize);
-    if (bitsize != 0) {
-	goto badarg;
-    }
-    if (bitoffs != 0) {
-	bytes = erts_get_aligned_binary_bytes(subject, &temp_alloc);
-    }
-    if (state_term != NIL) {
-	state_ptr = (BinaryFindState_bignum *)(big_val(state_term));
-	bfs = &(state_ptr->bfs);
+    if (ctx_bin == NULL) {
+	is_first_call = 1;
+	ctx = *ctxp;
+    } else {
+	is_first_call = 0;
+	ctx = ERTS_MAGIC_BIN_DATA(ctx_bin);
+	ctx->pat_bin = pat_bin;
+	*ctxp = ctx;
     }
 
-    if (bfs->flags & BINARY_FIND_ALL) {
-	if (bfs->type == am_bm) {
-	    BMData *bm;
-	    Sint pos;
-	    BMFindAllState state;
-	    Uint reds = get_reds(p, BM_LOOP_FACTOR);
-	    Uint save_reds = reds;
+    initial_reds = ctx->reds = get_reds(p, ctx->loop_factor);
 
-	    bm = (BMData *) ERTS_MAGIC_BIN_DATA(bin);
-#ifdef HARDDEBUG
-	    dump_bm_data(bm);
-#endif
-	    if (state_term == NIL) {
-		bm_init_find_all(&state, bfs->hsstart, bfs->hsend);
-	    } else {
-		bm_restore_find_all(&state, &(state_ptr->data.bmfas));
-	    }
+    switch (ctx->state) {
+    case BFSearch: {
+	byte *bytes;
+	Uint bitoffs, bitsize;
+	byte *temp_alloc = NULL;
 
-	    pos = bm_find_all_non_overlapping(&state, bm, bytes, &reds);
-	    if (pos == BM_NOT_FOUND) {
-		*res_term = bfs->not_found_result(p, subject, bfs);
-	    } else if (pos == BM_RESTART) {
-		int x =
-		    (SIZEOF_BINARY_FIND_ALL_STATE(state) / sizeof(Eterm)) +
-		    !!(SIZEOF_BINARY_FIND_ALL_STATE(state) % sizeof(Eterm));
-#ifdef HARDDEBUG
-		erts_printf("Trap bm!\n");
-#endif
-		state_ptr = (BinaryFindState_bignum*) HAlloc(p, x+1);
-		state_ptr->bignum_hdr = make_pos_bignum_header(x);
-		memcpy(&state_ptr->bfs, bfs, sizeof(BinaryFindState));
-		bm_serialize_find_all(&state, &state_ptr->data.bmfas);
-		*res_term = make_big(&state_ptr->bignum_hdr);
-		erts_free_aligned_binary_bytes(temp_alloc);
-		bm_clean_find_all(&state);
-		return DO_BIN_MATCH_RESTART;
-	    } else {
-		*res_term = bfs->global_result(p, subject, bfs, state.out, state.m);
-	    }
-	    erts_free_aligned_binary_bytes(temp_alloc);
-	    bm_clean_find_all(&state);
-	    BUMP_REDS(p, (save_reds - reds) / BM_LOOP_FACTOR);
-	    return DO_BIN_MATCH_OK;
-	} else if (bfs->type == am_ac) {
-	    ACTrie *act;
-	    int acr;
-	    ACFindAllState state;
-	    Uint reds = get_reds(p, AC_LOOP_FACTOR);
-	    Uint save_reds = reds;
-
-	    act = (ACTrie *) ERTS_MAGIC_BIN_DATA(bin);
+	ERTS_GET_BINARY_BYTES(subject, bytes, bitoffs, bitsize);
+	if (bitsize != 0) {
+	    goto badarg;
+	}
+	if (bitoffs != 0) {
+	    bytes = erts_get_aligned_binary_bytes(subject, &temp_alloc);
+	}
 #ifdef HARDDEBUG
-	    dump_ac_trie(act);
+	bf_context_dump(ctx);
 #endif
-	    if (state_term == NIL) {
-		ac_init_find_all(&state, act, bfs->hsstart, bfs->hsend);
-	    } else {
-		ac_restore_find_all(&state, &(state_ptr->data.acfas));
-	    }
-	    acr = ac_find_all_non_overlapping(&state, bytes, &reds);
-	    if (acr == AC_NOT_FOUND) {
-		*res_term = bfs->not_found_result(p, subject, bfs);
-	    } else if (acr == AC_RESTART) {
-		int x =
-		    (SIZEOF_BINARY_FIND_ALL_STATE(state) / sizeof(Eterm)) +
-		    !!(SIZEOF_BINARY_FIND_ALL_STATE(state) % sizeof(Eterm));
+	runres = ctx->search->find(ctx, bytes);
+	if (runres == BF_NOT_FOUND) {
+	    *res_term = ctx->not_found(p, subject, &ctx);
+	    *ctxp = ctx;
+	} else if (runres == BF_RESTART) {
 #ifdef HARDDEBUG
+	    if (ctx->pat_type == am_ac) {
 		erts_printf("Trap ac!\n");
-#endif
-                state_ptr = (BinaryFindState_bignum*) HAlloc(p, x+1);
-		state_ptr->bignum_hdr = make_pos_bignum_header(x);
-		memcpy(&state_ptr->bfs, bfs, sizeof(BinaryFindState));
-		ac_serialize_find_all(&state, &state_ptr->data.acfas);
-		*res_term = make_big(&state_ptr->bignum_hdr);
-		erts_free_aligned_binary_bytes(temp_alloc);
-		ac_clean_find_all(&state);
-		return DO_BIN_MATCH_RESTART;
-	    } else {
-		*res_term = bfs->global_result(p, subject, bfs, state.out, state.m);
-	    }
-	    erts_free_aligned_binary_bytes(temp_alloc);
-	    ac_clean_find_all(&state);
-	    BUMP_REDS(p, (save_reds - reds) / AC_LOOP_FACTOR);
-	    return DO_BIN_MATCH_OK;
-	}
-    } else {
-	if (bfs->type == am_bm) {
-	    BMData *bm;
-	    Sint pos;
-	    BMFindFirstState state;
-	    Uint reds = get_reds(p, BM_LOOP_FACTOR);
-	    Uint save_reds = reds;
-
-	    bm = (BMData *) ERTS_MAGIC_BIN_DATA(bin);
-#ifdef HARDDEBUG
-	    dump_bm_data(bm);
-#endif
-	    if (state_term == NIL) {
-		bm_init_find_first_match(&state, bfs->hsstart, bfs->hsend);
 	    } else {
-		memcpy(&state, &state_ptr->data.bmffs, sizeof(BMFindFirstState));
-	    }
-
-#ifdef HARDDEBUG
-	    erts_printf("(bm) state->pos = %ld, state->len = %lu\n",state.pos,
-			state.len);
-#endif
-	    pos = bm_find_first_match(&state, bm, bytes, &reds);
-	    if (pos == BM_NOT_FOUND) {
-		*res_term = bfs->not_found_result(p, subject, bfs);
-	    } else if (pos == BM_RESTART) {
-		int x =
-		    (SIZEOF_BINARY_FIND_STATE(state) / sizeof(Eterm)) +
-		    !!(SIZEOF_BINARY_FIND_STATE(state) % sizeof(Eterm));
-#ifdef HARDDEBUG
 		erts_printf("Trap bm!\n");
+	    }
 #endif
-                state_ptr = (BinaryFindState_bignum*) HAlloc(p, x+1);
-                state_ptr->bignum_hdr = make_pos_bignum_header(x);
-		memcpy(&state_ptr->bfs, bfs, sizeof(BinaryFindState));
-		memcpy(&state_ptr->data.acffs, &state, sizeof(BMFindFirstState));
-		*res_term = make_big(&state_ptr->bignum_hdr);
-		erts_free_aligned_binary_bytes(temp_alloc);
-		return DO_BIN_MATCH_RESTART;
-	    } else {
-		*res_term = bfs->single_result(p, subject, bfs, pos, bm->len);
+	    if (is_first_call) {
+		ctx = bf_context_export(p, ctx);
+		*ctxp = ctx;
+		erts_set_gc_state(p, 0);
 	    }
 	    erts_free_aligned_binary_bytes(temp_alloc);
-	    BUMP_REDS(p, (save_reds - reds) / BM_LOOP_FACTOR);
-	    return DO_BIN_MATCH_OK;
-	} else if (bfs->type == am_ac) {
-	    ACTrie *act;
-	    Uint pos, rlen;
-	    int acr;
-	    ACFindFirstState state;
-	    Uint reds = get_reds(p, AC_LOOP_FACTOR);
-	    Uint save_reds = reds;
-
-	    act = (ACTrie *) ERTS_MAGIC_BIN_DATA(bin);
-#ifdef HARDDEBUG
-	    dump_ac_trie(act);
-#endif
-	    if (state_term == NIL) {
-		ac_init_find_first_match(&state, act, bfs->hsstart, bfs->hsend);
-	    } else {
-		memcpy(&state, &state_ptr->data.acffs, sizeof(ACFindFirstState));
+	    *res_term = THE_NON_VALUE;
+	    BUMP_ALL_REDS(p);
+	    return BF_RESTART;
+	} else {
+	    *res_term = ctx->found(p, subject, &ctx);
+	    *ctxp = ctx;
+	}
+	erts_free_aligned_binary_bytes(temp_alloc);
+	if (*res_term == THE_NON_VALUE) {
+	    if (is_first_call) {
+		erts_set_gc_state(p, 0);
 	    }
-	    acr = ac_find_first_match(&state, bytes, &pos, &rlen, &reds);
-	    if (acr == AC_NOT_FOUND) {
-		*res_term = bfs->not_found_result(p, subject, bfs);
-	    } else if (acr == AC_RESTART) {
-		int x =
-		    (SIZEOF_BINARY_FIND_STATE(state) / sizeof(Eterm)) +
-		    !!(SIZEOF_BINARY_FIND_STATE(state) % sizeof(Eterm));
-#ifdef HARDDEBUG
-		erts_printf("Trap ac!\n");
-#endif
-		state_ptr = (BinaryFindState_bignum*) HAlloc(p, x+1);
-		state_ptr->bignum_hdr = make_pos_bignum_header(x);
-		memcpy(&state_ptr->bfs, bfs, sizeof(BinaryFindState));
-		memcpy(&state_ptr->data.acffs, &state, sizeof(ACFindFirstState));
-		*res_term = make_big(&state_ptr->bignum_hdr);
-		erts_free_aligned_binary_bytes(temp_alloc);
-		return DO_BIN_MATCH_RESTART;
-	    } else {
-		*res_term = bfs->single_result(p, subject, bfs, pos, rlen);
+	    BUMP_ALL_REDS(p);
+	    return BF_RESTART;
+	}
+	if (ctx->search->done != NULL) {
+	    ctx->search->done(ctx);
+	}
+	ctx->state = BFDone;
+	if (!is_first_call) {
+	    erts_set_gc_state(p, 1);
+	}
+	BUMP_REDS(p, (initial_reds - ctx->reds) / ctx->loop_factor);
+	return BF_OK;
+    }
+    case BFResult: {
+	*res_term = ctx->found(p, subject, &ctx);
+	*ctxp = ctx;
+	if (*res_term == THE_NON_VALUE) {
+	    if (is_first_call) {
+		erts_set_gc_state(p, 0);
 	    }
-	    erts_free_aligned_binary_bytes(temp_alloc);
-	    BUMP_REDS(p, (save_reds - reds) / AC_LOOP_FACTOR);
-	    return DO_BIN_MATCH_OK;
+	    BUMP_ALL_REDS(p);
+	    return BF_RESTART;
+	}
+	if (ctx->search->done != NULL) {
+	    ctx->search->done(ctx);
 	}
+	ctx->state = BFDone;
+	if (!is_first_call) {
+	    erts_set_gc_state(p, 1);
+	}
+	BUMP_REDS(p, (initial_reds - ctx->reds) / ctx->loop_factor);
+	return BF_OK;
     }
- badarg:
-    return DO_BIN_MATCH_BADARG;
+    default:
+	ASSERT(!"Unknown state in do_binary_find");
+    }
+
+badarg:
+    if (!is_first_call) {
+	if (ctx->search->done != NULL) {
+	    ctx->search->done(ctx);
+	}
+	ctx->state = BFDone;
+	erts_set_gc_state(p, 1);
+    }
+    return BF_BADARG;
 }
 
 static BIF_RETTYPE
 binary_match(Process *p, Eterm arg1, Eterm arg2, Eterm arg3, Uint flags)
 {
-    BinaryFindState bfs;
-    Eterm *tp;
-    Binary *bin;
-    Eterm bin_term = NIL;
+    BinaryFindContext c_buff;
+    BinaryFindContext *ctx = &c_buff;
+    Binary *pat_bin;
     int runres;
     Eterm result;
 
-    if (is_not_binary(arg1)) {
+    if (is_not_binary(arg1) || binary_bitsize(arg1) != 0) {
 	goto badarg;
     }
-    bfs.flags = flags;
-    if (parse_match_opts_list(arg3, arg1, &(bfs.hsstart), &(bfs.hsend))) {
+    ctx->flags = flags;
+    if (parse_match_opts_list(arg3, arg1, &(ctx->hsstart), &(ctx->hsend))) {
 	goto badarg;
     }
-    if (bfs.hsend == 0) {
-	BIF_RET(do_match_not_found_result(p, arg1, &bfs));
+    if (ctx->hsend == 0) {
+	result = do_match_not_found_result(p, arg1, &ctx);
+	BIF_RET(result);
     }
-    if (is_tuple(arg2)) {
-	tp = tuple_val(arg2);
-	if (arityval(*tp) != 2 || is_not_atom(tp[1])) {
-	    goto badarg;
-	}
-	if (((tp[1] != am_bm) && (tp[1] != am_ac)) ||
-	    !is_internal_magic_ref(tp[2])) {
-	    goto badarg;
-	}
-	bfs.type = tp[1];
-	bin = erts_magic_ref2bin(tp[2]);
-	if (bfs.type == am_bm &&
-	    ERTS_MAGIC_BIN_DESTRUCTOR(bin) != cleanup_my_data_bm) {
-	    goto badarg;
-	}
-	if (bfs.type == am_ac &&
-	    ERTS_MAGIC_BIN_DESTRUCTOR(bin) != cleanup_my_data_ac) {
-	    goto badarg;
-	}
-	bin_term = tp[2];
-    } else if (do_binary_match_compile(arg2, &(bfs.type), &bin)) {
+    if (maybe_binary_match_compile(ctx, arg2, &pat_bin) != BF_OK) {
 	goto badarg;
     }
-    bfs.not_found_result = &do_match_not_found_result;
-    bfs.single_result = &do_match_single_result;
-    bfs.global_result = &do_match_global_result;
-    runres = do_binary_find(p, arg1, &bfs, bin, NIL, &result);
-    if (runres == DO_BIN_MATCH_RESTART && bin_term == NIL) {
-	Eterm *hp = HAlloc(p, ERTS_MAGIC_REF_THING_SIZE);
-	bin_term = erts_mk_magic_ref(&hp, &MSO(p), bin);
-    } else if (bin_term == NIL) {
-	erts_bin_free(bin);
+    bf_context_init(ctx, do_match_not_found_result, do_match_single_result,
+		    do_match_global_result, pat_bin);
+    runres = do_binary_find(p, arg1, &ctx, pat_bin, NULL, &result);
+    if (runres == BF_OK && ctx->pat_term == THE_NON_VALUE) {
+	erts_bin_free(pat_bin);
     }
     switch (runres) {
-    case DO_BIN_MATCH_OK:
+    case BF_OK:
 	BIF_RET(result);
-    case DO_BIN_MATCH_RESTART:
-	BUMP_ALL_REDS(p);
-	BIF_TRAP3(&binary_find_trap_export, p, arg1, result, bin_term);
+    case BF_RESTART:
+	ASSERT(result == THE_NON_VALUE && ctx->trap_term != result && ctx->pat_term != result);
+	BIF_TRAP3(&binary_find_trap_export, p, arg1, ctx->trap_term, ctx->pat_term);
     default:
 	goto badarg;
     }
- badarg:
-    BIF_ERROR(p,BADARG);
+badarg:
+    BIF_ERROR(p, BADARG);
 }
 
 BIF_RETTYPE binary_match_2(BIF_ALIST_2)
@@ -1471,76 +1512,52 @@ BIF_RETTYPE binary_match_3(BIF_ALIST_3)
 
 BIF_RETTYPE binary_matches_2(BIF_ALIST_2)
 {
-    return binary_match(BIF_P, BIF_ARG_1, BIF_ARG_2, THE_NON_VALUE, BINARY_FIND_ALL);
+    return binary_match(BIF_P, BIF_ARG_1, BIF_ARG_2, THE_NON_VALUE, BF_FLAG_GLOBAL);
 }
 
 BIF_RETTYPE binary_matches_3(BIF_ALIST_3)
 {
-    return binary_match(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, BINARY_FIND_ALL);
+    return binary_match(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3, BF_FLAG_GLOBAL);
 }
 
 static BIF_RETTYPE
 binary_split(Process *p, Eterm arg1, Eterm arg2, Eterm arg3)
 {
-    BinaryFindState bfs;
-    Eterm *tp;
-    Binary *bin;
-    Eterm bin_term = NIL;
+    BinaryFindContext c_buff;
+    BinaryFindContext *ctx = &c_buff;
+    Binary *pat_bin;
     int runres;
     Eterm result;
 
-    if (is_not_binary(arg1)) {
+    if (is_not_binary(arg1) || binary_bitsize(arg1) != 0) {
 	goto badarg;
     }
-    if (parse_split_opts_list(arg3, arg1, &(bfs.hsstart), &(bfs.hsend), &(bfs.flags))) {
+    if (parse_split_opts_list(arg3, arg1, &(ctx->hsstart), &(ctx->hsend), &(ctx->flags))) {
 	goto badarg;
     }
-    if (bfs.hsend == 0) {
-	result = do_split_not_found_result(p, arg1, &bfs);
+    if (ctx->hsend == 0) {
+	result = do_split_not_found_result(p, arg1, &ctx);
 	BIF_RET(result);
     }
-    if (is_tuple(arg2)) {
-	tp = tuple_val(arg2);
-	if (arityval(*tp) != 2 || is_not_atom(tp[1])) {
-	    goto badarg;
-	}
-	if (((tp[1] != am_bm) && (tp[1] != am_ac)) ||
-	    !is_internal_magic_ref(tp[2])) {
-	    goto badarg;
-	}
-	bfs.type = tp[1];
-	bin = erts_magic_ref2bin(tp[2]);
-	if (bfs.type == am_bm &&
-	    ERTS_MAGIC_BIN_DESTRUCTOR(bin) != cleanup_my_data_bm) {
-	    goto badarg;
-	}
-	if (bfs.type == am_ac &&
-	    ERTS_MAGIC_BIN_DESTRUCTOR(bin) != cleanup_my_data_ac) {
-	    goto badarg;
-	}
-	bin_term = tp[2];
-    } else if (do_binary_match_compile(arg2, &(bfs.type), &bin)) {
+    if (maybe_binary_match_compile(ctx, arg2, &pat_bin) != BF_OK) {
 	goto badarg;
     }
-    bfs.not_found_result = &do_split_not_found_result;
-    bfs.single_result = &do_split_single_result;
-    bfs.global_result = &do_split_global_result;
-    runres = do_binary_find(p, arg1, &bfs, bin, NIL, &result);
-    if (runres == DO_BIN_MATCH_RESTART && bin_term == NIL) {
-	Eterm *hp = HAlloc(p, ERTS_MAGIC_REF_THING_SIZE);
-	bin_term = erts_mk_magic_ref(&hp, &MSO(p), bin);
-    } else if (bin_term == NIL) {
-	erts_bin_free(bin);
-    }
-    switch(runres) {
-    case DO_BIN_MATCH_OK:
+    bf_context_init(ctx, do_split_not_found_result, do_split_single_result,
+		    do_split_global_result, pat_bin);
+    runres = do_binary_find(p, arg1, &ctx, pat_bin, NULL, &result);
+    if (runres == BF_OK && ctx->pat_term == THE_NON_VALUE) {
+	erts_bin_free(pat_bin);
+    }
+    switch (runres) {
+    case BF_OK:
 	BIF_RET(result);
-    case DO_BIN_MATCH_RESTART:
-	BIF_TRAP3(&binary_find_trap_export, p, arg1, result, bin_term);
+    case BF_RESTART:
+	ASSERT(result == THE_NON_VALUE && ctx->trap_term != result && ctx->pat_term != result);
+	BIF_TRAP3(&binary_find_trap_export, p, arg1, ctx->trap_term, ctx->pat_term);
     default:
 	goto badarg;
     }
- badarg:
+badarg:
     BIF_ERROR(p, BADARG);
 }
 
@@ -1554,72 +1571,117 @@ BIF_RETTYPE binary_split_3(BIF_ALIST_3)
     return binary_split(BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3);
 }
 
-static Eterm do_match_not_found_result(Process *p, Eterm subject, BinaryFindState *bfs)
+static Eterm do_match_not_found_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
-    if (bfs->flags & BINARY_FIND_ALL) {
+    if ((*ctxp)->flags & BF_FLAG_GLOBAL) {
 	return NIL;
     } else {
 	return am_nomatch;
     }
 }
 
-static Eterm do_match_single_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    Sint pos, Sint len)
+static Eterm do_match_single_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
+    BinaryFindContext *ctx = (*ctxp);
+    BinaryFindFirstContext *ff = &(ctx->u.ff);
     Eterm erlen;
     Eterm *hp;
     Eterm ret;
 
-    erlen = erts_make_integer((Uint)(len), p);
-    ret = erts_make_integer(pos, p);
+    erlen = erts_make_integer((Uint)(ff->len), p);
+    ret = erts_make_integer(ff->pos, p);
     hp = HAlloc(p, 3);
     ret = TUPLE2(hp, ret, erlen);
 
     return ret;
 }
 
-static Eterm do_match_global_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    FindallData *fad, Uint fad_sz)
+static Eterm do_match_global_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
-    Sint i;
+    BinaryFindContext *ctx = (*ctxp);
+    BinaryFindAllContext *fa = &(ctx->u.fa);
+    FindallData *fad;
     Eterm tpl;
-    Eterm *hp;
-    Eterm ret;
+    Sint i;
+    register Uint reds = ctx->reds;
 
-    for (i = 0; i < fad_sz; ++i) {
-	fad[i].epos = erts_make_integer(fad[i].pos, p);
-	fad[i].elen = erts_make_integer(fad[i].len, p);
+    if (ctx->state == BFSearch) {
+	if (ctx->pat_type == am_ac) {
+	    fa->data = fa->d.ac.out;
+	    fa->size = fa->d.ac.m;
+	} else {
+	    fa->data = fa->d.bm.out;
+	    fa->size = fa->d.bm.m;
+	}
+	fa->tail = fa->size - 1;
+	fa->head = 0;
+	fa->end_pos = 0;
+	fa->term = NIL;
+	if (ctx->exported == 0 && ((fa->size * 2) >= reds)) {
+	    ctx = bf_context_export(p, ctx);
+	    *ctxp = ctx;
+	    fa = &(ctx->u.fa);
+	}
+	erts_factory_proc_prealloc_init(&(fa->factory), p, fa->size * (3 + 2));
+	ctx->state = BFResult;
+    }
+
+    fad = fa->data;
+
+    if (fa->end_pos == 0) {
+	for (i = fa->head; i < fa->size; ++i) {
+	    if (--reds == 0) {
+		ASSERT(ctx->exported == 1);
+		fa->head = i;
+		ctx->reds = reds;
+		return THE_NON_VALUE;
+	    }
+	    fad[i].epos = erts_make_integer(fad[i].pos, p);
+	    fad[i].elen = erts_make_integer(fad[i].len, p);
+	}
+	fa->end_pos = 1;
+	fa->head = fa->tail;
     }
-    hp = HAlloc(p, fad_sz * (3 + 2));
-    ret = NIL;
-    for (i = fad_sz - 1; i >= 0; --i) {
-	tpl = TUPLE2(hp, fad[i].epos, fad[i].elen);
-	hp += 3;
-	ret = CONS(hp, tpl, ret);
-	hp += 2;
+
+    for (i = fa->head; i >= 0; --i) {
+	if (--reds == 0) {
+	    ASSERT(ctx->exported == 1);
+	    fa->head = i;
+	    ctx->reds = reds;
+	    return THE_NON_VALUE;
+	}
+	tpl = TUPLE2(fa->factory.hp, fad[i].epos, fad[i].elen);
+	fa->factory.hp += 3;
+	fa->term = CONS(fa->factory.hp, tpl, fa->term);
+	fa->factory.hp += 2;
     }
+    ctx->reds = reds;
+    erts_factory_close(&(fa->factory));
 
-    return ret;
+    return fa->term;
 }
 
-static Eterm do_split_not_found_result(Process *p, Eterm subject, BinaryFindState *bfs)
+static Eterm do_split_not_found_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
+    BinaryFindContext *ctx = (*ctxp);
     Eterm *hp;
     Eterm ret;
 
-    if (bfs->flags & (BINARY_SPLIT_TRIM | BINARY_SPLIT_TRIM_ALL)
+    if (ctx->flags & (BF_FLAG_SPLIT_TRIM | BF_FLAG_SPLIT_TRIM_ALL)
         && binary_size(subject) == 0) {
-        return NIL;
+	return NIL;
     }
     hp = HAlloc(p, 2);
     ret = CONS(hp, subject, NIL);
-
     return ret;
 }
 
-static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    Sint pos, Sint len)
+static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
+    BinaryFindContext *ctx = (*ctxp);
+    BinaryFindFirstContext *ff = &(ctx->u.ff);
+    Sint pos;
+    Sint len;
     size_t orig_size;
     Eterm orig;
     Uint offset;
@@ -1630,9 +1692,12 @@ static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindState *
     Eterm *hp;
     Eterm ret;
 
+    pos = ff->pos;
+    len = ff->len;
+
     orig_size = binary_size(subject);
 
-    if ((bfs->flags & (BINARY_SPLIT_TRIM | BINARY_SPLIT_TRIM_ALL)) &&
+    if ((ctx->flags & (BF_FLAG_SPLIT_TRIM | BF_FLAG_SPLIT_TRIM_ALL)) &&
 	(orig_size - pos - len) == 0) {
 	if (pos == 0) {
 	    ret = NIL;
@@ -1653,7 +1718,7 @@ static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindState *
 	    hp += 2;
 	}
     } else {
-	if ((bfs->flags & BINARY_SPLIT_TRIM_ALL) && (pos == 0)) {
+	if ((ctx->flags & BF_FLAG_SPLIT_TRIM_ALL) && (pos == 0)) {
 	    hp = HAlloc(p, 1 * (ERL_SUB_BIN_SIZE + 2));
 	    ERTS_GET_REAL_BIN(subject, orig, offset, bit_offset, bit_size);
 	    sb1 = NULL;
@@ -1691,39 +1756,60 @@ static Eterm do_split_single_result(Process *p, Eterm subject, BinaryFindState *
     return ret;
 }
 
-static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindState *bfs,
-				    FindallData *fad, Uint fad_sz)
+static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindContext **ctxp)
 {
-    size_t orig_size;
+    BinaryFindContext *ctx = (*ctxp);
+    BinaryFindAllContext *fa = &(ctx->u.fa);
+    FindallData *fad;
     Eterm orig;
+    size_t orig_size;
     Uint offset;
     Uint bit_offset;
     Uint bit_size;
     ErlSubBin *sb;
+    Uint do_trim;
     Sint i;
-    Sint tail;
-    Uint list_size;
-    Uint end_pos;
-    Uint do_trim = bfs->flags & (BINARY_SPLIT_TRIM | BINARY_SPLIT_TRIM_ALL);
-    Eterm *hp;
-    Eterm *hendp;
-    Eterm ret;
+    register Uint reds = ctx->reds;
 
-    tail = fad_sz - 1;
-    list_size = fad_sz + 1;
-    orig_size = binary_size(subject);
-    end_pos = (Uint)(orig_size);
+    if (ctx->state == BFSearch) {
+	if (ctx->pat_type == am_ac) {
+	    fa->data = fa->d.ac.out;
+	    fa->size = fa->d.ac.m;
+	} else {
+	    fa->data = fa->d.bm.out;
+	    fa->size = fa->d.bm.m;
+	}
+	fa->tail = fa->size - 1;
+	fa->head = fa->tail;
+	orig_size = binary_size(subject);
+	fa->end_pos = (Uint)(orig_size);
+	fa->term = NIL;
+	if (ctx->exported == 0 && ((fa->head + 1) >= reds)) {
+	    ctx = bf_context_export(p, ctx);
+	    *ctxp = ctx;
+	    fa = &(ctx->u.fa);
+	}
+	erts_factory_proc_prealloc_init(&(fa->factory), p, (fa->size + 1) * (ERL_SUB_BIN_SIZE + 2));
+	ctx->state = BFResult;
+    }
 
-    hp = HAlloc(p, list_size * (ERL_SUB_BIN_SIZE + 2));
-    hendp = hp + list_size * (ERL_SUB_BIN_SIZE + 2);
     ERTS_GET_REAL_BIN(subject, orig, offset, bit_offset, bit_size);
     ASSERT(bit_size == 0);
+    fad = fa->data;
+    do_trim = ctx->flags & (BF_FLAG_SPLIT_TRIM | BF_FLAG_SPLIT_TRIM_ALL);
 
-    ret = NIL;
-
-    for (i = tail; i >= 0; --i) {
-	sb = (ErlSubBin *)(hp);
-	sb->size = end_pos - (fad[i].pos + fad[i].len);
+    for (i = fa->head; i >= 0; --i) {
+	if (--reds == 0) {
+	    ASSERT(ctx->exported == 1);
+	    fa->head = i;
+	    ctx->reds = reds;
+	    if (!do_trim && (ctx->flags & BF_FLAG_SPLIT_TRIM)) {
+		ctx->flags &= ~BF_FLAG_SPLIT_TRIM;
+	    }
+	    return THE_NON_VALUE;
+	}
+	sb = (ErlSubBin *)(fa->factory.hp);
+	sb->size = fa->end_pos - (fad[i].pos + fad[i].len);
 	if (!(sb->size == 0 && do_trim)) {
 	    sb->thing_word = HEADER_SUB_BIN;
 	    sb->offs = offset + fad[i].pos + fad[i].len;
@@ -1731,15 +1817,18 @@ static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindState *
 	    sb->bitoffs = bit_offset;
 	    sb->bitsize = 0;
 	    sb->is_writable = 0;
-	    hp += ERL_SUB_BIN_SIZE;
-	    ret = CONS(hp, make_binary(sb), ret);
-	    hp += 2;
-	    do_trim &= ~BINARY_SPLIT_TRIM;
+	    fa->factory.hp += ERL_SUB_BIN_SIZE;
+	    fa->term = CONS(fa->factory.hp, make_binary(sb), fa->term);
+	    fa->factory.hp += 2;
+	    do_trim &= ~BF_FLAG_SPLIT_TRIM;
 	}
-	end_pos = fad[i].pos;
+	fa->end_pos = fad[i].pos;
     }
 
-    sb = (ErlSubBin *)(hp);
+    fa->head = i;
+    ctx->reds = reds;
+
+    sb = (ErlSubBin *)(fa->factory.hp);
     sb->size = fad[0].pos;
     if (!(sb->size == 0 && do_trim)) {
 	sb->thing_word = HEADER_SUB_BIN;
@@ -1748,26 +1837,31 @@ static Eterm do_split_global_result(Process *p, Eterm subject, BinaryFindState *
 	sb->bitoffs = bit_offset;
 	sb->bitsize = 0;
 	sb->is_writable = 0;
-	hp += ERL_SUB_BIN_SIZE;
-	ret = CONS(hp, make_binary(sb), ret);
-	hp += 2;
+	fa->factory.hp += ERL_SUB_BIN_SIZE;
+	fa->term = CONS(fa->factory.hp, make_binary(sb), fa->term);
+	fa->factory.hp += 2;
     }
-    HRelease(p, hendp, hp);
-    return ret;
+    erts_factory_close(&(fa->factory));
+
+    return fa->term;
 }
 
 static BIF_RETTYPE binary_find_trap(BIF_ALIST_3)
 {
     int runres;
     Eterm result;
-    Binary *bin = erts_magic_ref2bin(BIF_ARG_3);
-
-    runres = do_binary_find(BIF_P, BIF_ARG_1, NULL, bin, BIF_ARG_2, &result);
-    if (runres == DO_BIN_MATCH_OK) {
+    Binary *ctx_bin = erts_magic_ref2bin(BIF_ARG_2);
+    Binary *pat_bin = erts_magic_ref2bin(BIF_ARG_3);
+    BinaryFindContext *ctx = NULL;
+
+    ASSERT(ERTS_MAGIC_BIN_DESTRUCTOR(ctx_bin) == bf_context_destructor);
+    runres = do_binary_find(BIF_P, BIF_ARG_1, &ctx, pat_bin, ctx_bin, &result);
+    if (runres == BF_OK) {
+	ASSERT(result != THE_NON_VALUE);
 	BIF_RET(result);
     } else {
-	BUMP_ALL_REDS(BIF_P);
-	BIF_TRAP3(&binary_find_trap_export, BIF_P, BIF_ARG_1, result, BIF_ARG_3);
+	ASSERT(result == THE_NON_VALUE && ctx->trap_term != result && ctx->pat_term != result);
+	BIF_TRAP3(&binary_find_trap_export, BIF_P, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3);
     }
 }