Add binary:longest_common_prefix/longest_common_suffix

Add allcoator parameter to erts_get_aligned_binary_bytes_extra.
Add testcases for the functions above.
Add reference implementation for the functions above.

7 files changed, 337 insertions, 10 deletions

diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names
index 06ff0e11a4..386b040a27 100644
--- a/erts/emulator/beam/atom.names
+++ b/erts/emulator/beam/atom.names
@@ -101,6 +101,8 @@ atom band
 atom big
 atom bif_return_trap
 atom binary
+atom binary_longest_prefix_trap
+atom binary_longest_suffix_trap
 atom binary_match_trap
 atom binary_matches_trap
 atom block
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 85674664e4..536f9ac5c8 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -765,8 +765,8 @@ bif binary:match/2
 bif binary:match/3
 bif binary:matches/2
 bif binary:matches/3
-#  bif binary:longest_common_prefix/1
-#  bif binary:longest_common_suffix/1
+bif binary:longest_common_prefix/1
+bif binary:longest_common_suffix/1
 #  bif binary:first/1
 #  bif binary:last/1
 #  bif binary:at/2
diff --git a/erts/emulator/beam/binary.c b/erts/emulator/beam/binary.c
index 7ca3eb686d..9c4076c8ff 100644
--- a/erts/emulator/beam/binary.c
+++ b/erts/emulator/beam/binary.c
@@ -180,7 +180,7 @@ erts_realloc_binary(Eterm bin, size_t size)
 }
 
 byte*
-erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, unsigned extra)
+erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, ErtsAlcType_t allocator, unsigned extra)
 {
     byte* bytes;
     Eterm* real_bin;
@@ -208,7 +208,7 @@ erts_get_aligned_binary_bytes_extra(Eterm bin, byte** base_ptr, unsigned extra)
 	bytes = (byte *)(&(((ErlHeapBin *) real_bin)->data)) + offs;
     }
     if (bit_offs) {
-	byte* buf = (byte *) erts_alloc(ERTS_ALC_T_TMP, byte_size + extra);
+	byte* buf = (byte *) erts_alloc(allocator, byte_size + extra);
 	*base_ptr = buf;
 	buf += extra;
 	erts_copy_bits(bytes, bit_offs, 1, buf, 0, 1, byte_size*8);	
diff --git a/erts/emulator/beam/erl_alloc.types b/erts/emulator/beam/erl_alloc.types
index 5d2872a4e3..6f88bbe5b8 100644
--- a/erts/emulator/beam/erl_alloc.types
+++ b/erts/emulator/beam/erl_alloc.types
@@ -232,6 +232,7 @@ type    RE_SUBJECT      SHORT_LIVED     SYSTEM          re_subject
 type  	RE_HEAP 	STANDARD	SYSTEM		re_heap
 type	RE_STACK 	SHORT_LIVED	SYSTEM		re_stack
 type	UNICODE_BUFFER 	SHORT_LIVED	SYSTEM		unicode_buffer
+type	BINARY_BUFFER 	SHORT_LIVED	SYSTEM		binary_buffer
 type	PRE_ALLOC_DATA	LONG_LIVED	SYSTEM		pre_alloc_data
 type	DRV_THR_OPTS	DRIVER		SYSTEM		driver_thread_opts
 type	DRV_TID		DRIVER		SYSTEM		driver_tid
diff --git a/erts/emulator/beam/erl_bif_binary.c b/erts/emulator/beam/erl_bif_binary.c
index a635280ac1..5bde065049 100644
--- a/erts/emulator/beam/erl_bif_binary.c
+++ b/erts/emulator/beam/erl_bif_binary.c
@@ -55,6 +55,10 @@ static Export binary_match_trap_export;
 static BIF_RETTYPE binary_match_trap(BIF_ALIST_3);
 static Export binary_matches_trap_export;
 static BIF_RETTYPE binary_matches_trap(BIF_ALIST_3);
+static Export binary_longest_prefix_trap_export;
+static BIF_RETTYPE binary_longest_prefix_trap(BIF_ALIST_3);
+static Export binary_longest_suffix_trap_export;
+static BIF_RETTYPE binary_longest_suffix_trap(BIF_ALIST_3);
 static Uint max_loop_limit;
 
 
@@ -76,6 +80,22 @@ void erts_init_bif_binary(void)
     binary_matches_trap_export.code[3] = (BeamInstr) em_apply_bif;
     binary_matches_trap_export.code[4] = (BeamInstr) &binary_matches_trap;
 
+    sys_memset((void *) &binary_longest_prefix_trap_export, 0, sizeof(Export));
+    binary_longest_prefix_trap_export.address = &binary_longest_prefix_trap_export.code[3];
+    binary_longest_prefix_trap_export.code[0] = am_erlang;
+    binary_longest_prefix_trap_export.code[1] = am_binary_longest_prefix_trap;
+    binary_longest_prefix_trap_export.code[2] = 3;
+    binary_longest_prefix_trap_export.code[3] = (BeamInstr) em_apply_bif;
+    binary_longest_prefix_trap_export.code[4] = (BeamInstr) &binary_longest_prefix_trap;
+
+    sys_memset((void *) &binary_longest_suffix_trap_export, 0, sizeof(Export));
+    binary_longest_suffix_trap_export.address = &binary_longest_suffix_trap_export.code[3];
+    binary_longest_suffix_trap_export.code[0] = am_erlang;
+    binary_longest_suffix_trap_export.code[1] = am_binary_longest_suffix_trap;
+    binary_longest_suffix_trap_export.code[2] = 3;
+    binary_longest_suffix_trap_export.code[3] = (BeamInstr) em_apply_bif;
+    binary_longest_suffix_trap_export.code[4] = (BeamInstr) &binary_longest_suffix_trap;
+
     max_loop_limit = 0;
     return;
 }
@@ -1549,6 +1569,303 @@ BIF_RETTYPE binary_part_2(BIF_ALIST_2)
    BIF_ERROR(BIF_P,BADARG);
 }
 
+typedef struct {
+    int type;            /* CL_TYPE_XXX */
+    byte *temp_alloc;    /* Used for erts_get/free_aligned, i.e. CL_TYPE_ALIGNED */
+    unsigned char *buff; /* Used for all types, malloced if CL_TYPE_HEAP */
+    Uint bufflen;        /* The length (in bytes) of buffer */
+} CommonData;
+
+#define COMMON_LOOP_FACTOR 10
+
+#define DIRECTION_PREFIX 0
+#define DIRECTION_SUFFIX 1
+
+#define CL_OK 0
+#define CL_RESTART 1
+
+/* The type field in the above structure */
+#define CL_TYPE_EMPTY 0 /* End of array */
+#define CL_TYPE_HEAP 1
+#define CL_TYPE_ALIGNED 2
+#define CL_TYPE_COMMON 3 /* emacsulated */
+#define CL_TYPE_HEAP_NOALLOC 4 /* Will need allocating when trapping */
+
+
+static int do_search_forward(CommonData *cd, Uint *posp, Uint *redsp)
+{
+    Uint pos = *posp;
+    Sint reds = (Sint) *redsp;
+    int i;
+    unsigned char current = 0;
+
+    for(;;) {
+	for(i = 0; cd[i].type != CL_TYPE_EMPTY; ++i) {
+	    if (pos >= cd[i].bufflen) {
+		*posp = pos;
+		if (reds > 0) {
+		    *redsp = (Uint) reds;
+		} else {
+		    *redsp = 0;
+		}
+		return CL_OK;
+	    }
+	    if (i == 0) {
+		current = cd[i].buff[pos];
+	    } else {
+		if (cd[i].buff[pos] != current) {
+		    *posp = pos;
+		    if (reds > 0) {
+			*redsp = (Uint) reds;
+		    } else {
+			*redsp = 0;
+		    }
+		    return CL_OK;
+		}
+	    }
+	    --reds;
+	}
+	++pos;
+	if (reds <= 0) {
+	    *posp = pos;
+	    *redsp = 0;
+	    return CL_RESTART;
+	}
+    }
+}
+static int do_search_backward(CommonData *cd, Uint *posp, Uint *redsp)
+{
+    Uint pos = *posp;
+    Sint reds = (Sint) *redsp;
+    int i;
+    unsigned char current = 0;
+
+    for(;;) {
+	for(i = 0; cd[i].type != CL_TYPE_EMPTY; ++i) {
+	    if (pos >= cd[i].bufflen) {
+		*posp = pos;
+		if (reds > 0) {
+		    *redsp = (Uint) reds;
+		} else {
+		    *redsp = 0;
+		}
+		return CL_OK;
+	    }
+	    if (i == 0) {
+		current = cd[i].buff[cd[i].bufflen - 1 - pos];
+	    } else {
+		if (cd[i].buff[cd[i].bufflen - 1 - pos] != current) {
+		    *posp = pos;
+		    if (reds > 0) {
+			*redsp = (Uint) reds;
+		    } else {
+			*redsp = 0;
+		    }
+		    return CL_OK;
+		}
+	    }
+	    --reds;
+	}
+	++pos;
+	if (reds <= 0) {
+	    *posp = pos;
+	    *redsp = 0;
+	    return CL_RESTART;
+	}
+    }
+}
+
+static void cleanup_common_data(Binary *bp)
+{
+    int i;
+    CommonData *cd;
+    cd = (CommonData *) ERTS_MAGIC_BIN_DATA(bp);
+    for (i=0;cd[i].type != CL_TYPE_EMPTY;++i) {
+	switch (cd[i].type) {
+	case CL_TYPE_HEAP:
+	    erts_free(ERTS_ALC_T_BINARY_BUFFER,cd[i].buff);
+	    break;
+	case CL_TYPE_ALIGNED:
+	    erts_free_aligned_binary_bytes_extra(cd[i].temp_alloc, ERTS_ALC_T_BINARY_BUFFER);
+	    break;
+	default:
+	    break;
+	}
+    }
+    return;
+}
+
+static BIF_RETTYPE do_longest_common(Process *p, Eterm list, int direction)
+{
+    Eterm l = list;
+    int n = 0;
+    Binary *mb;
+    CommonData *cd;
+    int i = 0;
+    Uint reds = get_reds(p, COMMON_LOOP_FACTOR);
+    Uint save_reds = reds;
+    int res;
+    Export *trapper;
+    Uint pos;
+    Eterm epos;
+    Eterm *hp;
+    Eterm bin_term;
+    Eterm b;
+
+    /* First just count the number of binaries */
+    while (is_list(l)) {
+	b = CAR(list_val(l));
+	if (!is_binary(b)) {
+	    goto badarg;
+	}
+	++n;
+	l = CDR(list_val(l));
+    }
+    if (l != NIL || n == 0) {
+	goto badarg;
+    }
+
+    /* OK, now create a buffer of the right size, we can do a magic binary right away,
+       thats not to costly. */
+    mb = erts_create_magic_binary((n+1)*sizeof(CommonData),cleanup_common_data);
+    cd = (CommonData *) ERTS_MAGIC_BIN_DATA(mb);
+    l = list;
+    while (is_list(l)) {
+	Uint bitoffs;
+	Uint bitsize;
+	Uint offset;
+	Eterm real_bin;
+	ProcBin* pb;
+
+	cd[i].type = CL_TYPE_EMPTY;
+	b = CAR(list_val(l));
+	ERTS_GET_REAL_BIN(b, real_bin, offset, bitoffs, bitsize);
+	if (bitsize != 0) {
+	    erts_bin_free(mb);
+	    goto badarg;
+	}
+	cd[i].bufflen = binary_size(b);
+	cd[i].temp_alloc = NULL;
+	if (*(binary_val(real_bin)) == HEADER_PROC_BIN) {
+	    pb = (ProcBin *) binary_val(real_bin);
+	    if (pb->flags) {
+		erts_emasculate_writable_binary(pb);
+	    }
+	    cd[i].buff = erts_get_aligned_binary_bytes_extra(b, &(cd[i].temp_alloc),
+							     ERTS_ALC_T_BINARY_BUFFER,0);
+	    cd[i].type = (cd[i].temp_alloc != NULL) ? CL_TYPE_ALIGNED : CL_TYPE_COMMON;
+	} else { /* Heap binary */
+	    cd[i].buff = erts_get_aligned_binary_bytes_extra(b, &(cd[i].temp_alloc),
+							     ERTS_ALC_T_BINARY_BUFFER,0);
+	    /* CL_TYPE_HEAP_NOALLOC means you have to copy if trapping */
+	    cd[i].type = (cd[i].temp_alloc != NULL) ? CL_TYPE_ALIGNED : CL_TYPE_HEAP_NOALLOC;
+	}
+	++i;
+	l = CDR(list_val(l));
+    }
+    cd[i].type = CL_TYPE_EMPTY;
+#if defined(DEBUG) || defined(VALGRIND)
+    cd[i].temp_alloc = NULL;
+    cd[i].buff = NULL;
+    cd[i].bufflen = 0;
+#endif
+
+    pos = 0;
+    if (direction == DIRECTION_PREFIX) {
+	trapper = &binary_longest_prefix_trap_export;
+	res = do_search_forward(cd,&pos,&reds);
+    } else {
+	ASSERT(direction == DIRECTION_SUFFIX);
+	trapper = &binary_longest_suffix_trap_export;
+	res = do_search_backward(cd,&pos,&reds);
+    }
+    epos = erts_make_integer(pos,p);
+    if (res == CL_OK) {
+	erts_bin_free(mb);
+	BUMP_REDS(p, (save_reds - reds) / COMMON_LOOP_FACTOR);
+	BIF_RET(epos);
+    } else {
+	ASSERT(res == CL_RESTART);
+	/* Copy all heap binaries that are not already copied (aligned) */
+	for(i = 0; i < n; ++i) {
+	    if (cd[i].type == CL_TYPE_HEAP_NOALLOC) {
+		unsigned char *tmp = cd[i].buff;
+		cd[i].buff = erts_alloc(ERTS_ALC_T_BINARY_BUFFER, cd[i].bufflen);
+		memcpy(cd[i].buff,tmp,cd[i].bufflen);
+	    }
+	}
+	hp = HAlloc(p, PROC_BIN_SIZE);
+	bin_term = erts_mk_magic_binary_term(&hp, &MSO(p), mb);
+	BUMP_ALL_REDS(p);
+	BIF_TRAP3(trapper, p, bin_term, epos,list);
+    }
+ badarg:
+    BIF_ERROR(p,BADARG);
+}
+
+static BIF_RETTYPE do_longest_common_trap(Process *p, Eterm bin_term, Eterm current_pos,
+					  Eterm orig_list, int direction)
+{
+    Uint reds = get_reds(p, COMMON_LOOP_FACTOR);
+    Uint save_reds = reds;
+    Uint pos;
+    Binary *bin;
+    CommonData *cd;
+    int res;
+    Eterm epos;
+    Export *trapper;
+
+#ifdef DEBUG
+    int r;
+    r = term_to_Uint(current_pos, &pos);
+    ASSERT(r != 0);
+#else
+    term_to_Uint(current_pos, &pos);
+#endif
+    ASSERT(ERTS_TERM_IS_MAGIC_BINARY(bin_term));
+    bin = ((ProcBin *) binary_val(bin_term))->val;
+    cd = (CommonData *) ERTS_MAGIC_BIN_DATA(bin);
+    if (direction == DIRECTION_PREFIX) {
+	trapper = &binary_longest_prefix_trap_export;
+	res = do_search_forward(cd,&pos,&reds);
+    } else {
+	ASSERT(direction == DIRECTION_SUFFIX);
+	trapper = &binary_longest_suffix_trap_export;
+	res = do_search_backward(cd,&pos,&reds);
+    }
+    epos = erts_make_integer(pos,p);
+    if (res == CL_OK) {
+	BUMP_REDS(p, (save_reds - reds) / COMMON_LOOP_FACTOR);
+	BIF_RET(epos);
+    } else {
+	ASSERT(res == CL_RESTART);
+	/* Copy all heap binaries that are not already copied (aligned) */
+	BUMP_ALL_REDS(p);
+	BIF_TRAP3(&binary_longest_prefix_trap_export, p, bin_term, epos, orig_list);
+    }
+}
+
+static BIF_RETTYPE binary_longest_prefix_trap(BIF_ALIST_3)
+{
+    return do_longest_common_trap(BIF_P,BIF_ARG_1,BIF_ARG_2,BIF_ARG_3,DIRECTION_PREFIX);
+}
+
+static BIF_RETTYPE binary_longest_suffix_trap(BIF_ALIST_3)
+{
+    return do_longest_common_trap(BIF_P,BIF_ARG_1,BIF_ARG_2,BIF_ARG_3,DIRECTION_SUFFIX);
+}
+
+BIF_RETTYPE binary_longest_common_prefix_1(BIF_ALIST_1)
+{
+    return do_longest_common(BIF_P,BIF_ARG_1,DIRECTION_PREFIX);
+}
+
+BIF_RETTYPE binary_longest_common_suffix_1(BIF_ALIST_1)
+{
+    return do_longest_common(BIF_P,BIF_ARG_1,DIRECTION_SUFFIX);
+}
+
+
 
 /*
  * Hard debug functions (dump) for the search structures
diff --git a/erts/emulator/beam/erl_binary.h b/erts/emulator/beam/erl_binary.h
index 5b0b3bcec2..74d7966ca0 100644
--- a/erts/emulator/beam/erl_binary.h
+++ b/erts/emulator/beam/erl_binary.h
@@ -150,7 +150,7 @@ do {									\
 
 void erts_init_binary(void);
 
-byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, unsigned extra);
+byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, ErtsAlcType_t, unsigned extra);
 
 #if defined(__i386__) || !defined(__GNUC__)
 /*
@@ -168,6 +168,7 @@ byte* erts_get_aligned_binary_bytes_extra(Eterm, byte**, unsigned extra);
 
 ERTS_GLB_INLINE byte* erts_get_aligned_binary_bytes(Eterm bin, byte** base_ptr);
 ERTS_GLB_INLINE void erts_free_aligned_binary_bytes(byte* buf);
+ERTS_GLB_INLINE void erts_free_aligned_binary_bytes_extra(byte* buf, ErtsAlcType_t);
 ERTS_GLB_INLINE Binary *erts_bin_drv_alloc_fnf(Uint size);
 ERTS_GLB_INLINE Binary *erts_bin_drv_alloc(Uint size);
 ERTS_GLB_INLINE Binary *erts_bin_nrml_alloc(Uint size);
@@ -184,17 +185,23 @@ ERTS_GLB_INLINE Binary *erts_create_magic_binary(Uint size,
 ERTS_GLB_INLINE byte*
 erts_get_aligned_binary_bytes(Eterm bin, byte** base_ptr)
 {
-    return erts_get_aligned_binary_bytes_extra(bin, base_ptr, 0);
+    return erts_get_aligned_binary_bytes_extra(bin, base_ptr, ERTS_ALC_T_TMP, 0);
 }
 
 ERTS_GLB_INLINE void
-erts_free_aligned_binary_bytes(byte* buf)
+erts_free_aligned_binary_bytes_extra(byte* buf, ErtsAlcType_t allocator)
 {
     if (buf) {
-	erts_free(ERTS_ALC_T_TMP, (void *) buf);
+	erts_free(allocator, (void *) buf);
     }
 }
 
+ERTS_GLB_INLINE void
+erts_free_aligned_binary_bytes(byte* buf)
+{
+    erts_free_aligned_binary_bytes_extra(buf,ERTS_ALC_T_TMP);
+}
+
 /* Explicit extra bytes allocated to counter buggy drivers.
 ** These extra bytes where earlier (< R13B04) added by an alignment-bug
 ** in this code. Do we dare remove this in some major release (R14?) maybe?
diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c
index 2790020117..cee4df72a2 100644
--- a/erts/emulator/beam/erl_nif.c
+++ b/erts/emulator/beam/erl_nif.c
@@ -250,7 +250,7 @@ int enif_is_ref(ErlNifEnv* env, ERL_NIF_TERM term)
 
 static void aligned_binary_dtor(struct enif_tmp_obj_t* obj)
 {
-    erts_free_aligned_binary_bytes((byte*)obj);
+    erts_free_aligned_binary_bytes_extra((byte*)obj,ERTS_ALC_T_TMP);
 }
 
 int enif_inspect_binary(ErlNifEnv* env, Eterm bin_term, ErlNifBinary* bin)
@@ -260,7 +260,7 @@ int enif_inspect_binary(ErlNifEnv* env, Eterm bin_term, ErlNifBinary* bin)
 	byte* raw_ptr;
     }u;
     u.tmp = NULL;
-    bin->data = erts_get_aligned_binary_bytes_extra(bin_term, &u.raw_ptr,
+    bin->data = erts_get_aligned_binary_bytes_extra(bin_term, &u.raw_ptr, ERTS_ALC_T_TMP,
 						    sizeof(struct enif_tmp_obj_t));
     if (bin->data == NULL) {
 	return 0;