Index: contrib/elftoolchain/elfcopy/ascii.c
===================================================================
--- contrib/elftoolchain/elfcopy/ascii.c
+++ contrib/elftoolchain/elfcopy/ascii.c
@@ -378,9 +378,6 @@
 		errx(EXIT_FAILURE, "gelf_update_ehdr() failed: %s",
 		    elf_errmsg(-1));
 
-	/* Generate section name string table (.shstrtab). */
-	set_shstrtab(ecp);
-
 	/* Update sh_name pointer for each section header entry. */
 	update_shdr(ecp, 0);
 
@@ -605,9 +602,6 @@
 		errx(EXIT_FAILURE, "gelf_update_ehdr() failed: %s",
 		    elf_errmsg(-1));
 
-	/* Generate section name string table (.shstrtab). */
-	set_shstrtab(ecp);
-
 	/* Update sh_name pointer for each section header entry. */
 	update_shdr(ecp, 0);
 
Index: contrib/elftoolchain/elfcopy/binary.c
===================================================================
--- contrib/elftoolchain/elfcopy/binary.c
+++ contrib/elftoolchain/elfcopy/binary.c
@@ -250,11 +250,8 @@
 		errx(EXIT_FAILURE, "gelf_update_ehdr() failed: %s",
 		    elf_errmsg(-1));
 
-	/* Generate section name string table (.shstrtab). */
-	ecp->flags |= SYMTAB_EXIST;
-	set_shstrtab(ecp);
-
 	/* Update sh_name pointer for each section header entry. */
+	ecp->flags |= SYMTAB_EXIST;
 	update_shdr(ecp, 0);
 
 	/* Properly set sh_link field of .symtab section. */
Index: contrib/elftoolchain/elfcopy/elfcopy.h
===================================================================
--- contrib/elftoolchain/elfcopy/elfcopy.h
+++ contrib/elftoolchain/elfcopy/elfcopy.h
@@ -135,6 +135,8 @@
 	int		 pseudo;
 	int		 nocopy;
 
+	Elftc_String_Table *strtab;
+
 	TAILQ_ENTRY(section) sec_list;	/* next section */
 };
 
@@ -313,7 +315,6 @@
 struct symop *lookup_symop_list(struct elfcopy *_ecp, const char *_name,
     unsigned int _op);
 void	resync_sections(struct elfcopy *_ecp);
-void	set_shstrtab(struct elfcopy *_ecp);
 void	setup_phdr(struct elfcopy *_ecp);
 void	update_shdr(struct elfcopy *_ecp, int _update_link);
 
Index: contrib/elftoolchain/elfcopy/main.c
===================================================================
--- contrib/elftoolchain/elfcopy/main.c
+++ contrib/elftoolchain/elfcopy/main.c
@@ -388,9 +388,6 @@
 	 */
 	copy_content(ecp);
 
-	/* Generate section name string table (.shstrtab). */
-	set_shstrtab(ecp);
-
 	/*
 	 * Second processing of output sections: Update section headers.
 	 * At this stage we set name string index, update st_link and st_info
@@ -500,6 +497,8 @@
 		}
 	}
 
+	elftc_string_table_destroy(ecp->shstrtab->strtab);
+
 	ecp->symtab = NULL;
 	ecp->strtab = NULL;
 	ecp->shstrtab = NULL;
Index: contrib/elftoolchain/elfcopy/sections.c
===================================================================
--- contrib/elftoolchain/elfcopy/sections.c
+++ contrib/elftoolchain/elfcopy/sections.c
@@ -42,19 +42,18 @@
 static void	filter_reloc(struct elfcopy *ecp, struct section *s);
 static int	get_section_flags(struct elfcopy *ecp, const char *name);
 static void	insert_sections(struct elfcopy *ecp);
-static void	insert_to_strtab(struct section *t, const char *s);
 static int	is_append_section(struct elfcopy *ecp, const char *name);
 static int	is_compress_section(struct elfcopy *ecp, const char *name);
 static int	is_debug_section(const char *name);
 static int	is_dwo_section(const char *name);
 static int	is_modify_section(struct elfcopy *ecp, const char *name);
 static int	is_print_section(struct elfcopy *ecp, const char *name);
-static int	lookup_string(struct section *t, const char *s);
 static void	modify_section(struct elfcopy *ecp, struct section *s);
 static void	pad_section(struct elfcopy *ecp, struct section *s);
 static void	print_data(const char *d, size_t sz);
 static void	print_section(struct section *s);
 static void	*read_section(struct section *s, size_t *size);
+static void	set_shstrtab(struct elfcopy *ecp);
 static void	update_reloc(struct elfcopy *ecp, struct section *s);
 static void	update_section_group(struct elfcopy *ecp, struct section *s);
 
@@ -1336,10 +1335,9 @@
 void
 add_to_shstrtab(struct elfcopy *ecp, const char *name)
 {
-	struct section *s;
 
-	s = ecp->shstrtab;
-	insert_to_strtab(s, name);
+	if (elftc_string_table_insert(ecp->shstrtab->strtab, name) == 0)
+		errx(EXIT_FAILURE, "elftc_string_table_insert failed");
 }
 
 void
@@ -1349,6 +1347,9 @@
 	GElf_Shdr	 osh;
 	int		 elferr;
 
+	/* Finalize the section name string table (.shstrtab). */
+	set_shstrtab(ecp);
+
 	TAILQ_FOREACH(s, &ecp->v_sec, sec_list) {
 		if (s->pseudo)
 			continue;
@@ -1358,7 +1359,8 @@
 			    elf_errmsg(-1));
 
 		/* Find section name in string table and set sh_name. */
-		osh.sh_name = lookup_string(ecp->shstrtab, s->name);
+		osh.sh_name = elftc_string_table_lookup(ecp->shstrtab->strtab,
+		    s->name);
 
 		/*
 		 * sh_link needs to be updated, since the index of the
@@ -1408,19 +1410,21 @@
 	s->loadable = 0;
 	s->type = SHT_STRTAB;
 	s->vma = 0;
+	s->strtab = elftc_string_table_create(0);
 
-	insert_to_strtab(s, "");
-	insert_to_strtab(s, ".symtab");
-	insert_to_strtab(s, ".strtab");
-	insert_to_strtab(s, ".shstrtab");
+	add_to_shstrtab(ecp, "");
+	add_to_shstrtab(ecp, ".symtab");
+	add_to_shstrtab(ecp, ".strtab");
+	add_to_shstrtab(ecp, ".shstrtab");
 }
 
-void
+static void
 set_shstrtab(struct elfcopy *ecp)
 {
 	struct section	*s;
 	Elf_Data	*data;
 	GElf_Shdr	 sh;
+	const char	*image;
 
 	s = ecp->shstrtab;
 
@@ -1453,18 +1457,19 @@
 	 * which are reserved for this in the beginning of shstrtab.
 	 */
 	if (!(ecp->flags & SYMTAB_EXIST)) {
-		s->sz -= sizeof(".symtab\0.strtab");
-		memmove(s->buf, (char *)s->buf + sizeof(".symtab\0.strtab"),
-		    s->sz);
+		elftc_string_table_remove(s->strtab, ".symtab");
+		elftc_string_table_remove(s->strtab, ".strtab");
 	}
 
+	image = elftc_string_table_image(s->strtab, &s->sz);
+
 	sh.sh_size	= s->sz;
 	if (!gelf_update_shdr(s->os, &sh))
 		errx(EXIT_FAILURE, "gelf_update_shdr() failed: %s",
 		    elf_errmsg(-1));
 
 	data->d_align	= 1;
-	data->d_buf	= s->buf;
+	data->d_buf	= (void *)(uintptr_t)image;
 	data->d_size	= s->sz;
 	data->d_off	= 0;
 	data->d_type	= ELF_T_BYTE;
@@ -1591,73 +1596,6 @@
 	ecp->flags |= SEC_ADD;
 }
 
-static void
-insert_to_strtab(struct section *t, const char *s)
-{
-	const char	*r;
-	char		*b, *c;
-	size_t		 len, slen;
-	int		 append;
-
-	if (t->sz == 0) {
-		t->cap = 512;
-		if ((t->buf = malloc(t->cap)) == NULL)
-			err(EXIT_FAILURE, "malloc failed");
-	}
-
-	slen = strlen(s);
-	append = 0;
-	b = t->buf;
-	for (c = b; c < b + t->sz;) {
-		len = strlen(c);
-		if (!append && len >= slen) {
-			r = c + (len - slen);
-			if (strcmp(r, s) == 0)
-				return;
-		} else if (len < slen && len != 0) {
-			r = s + (slen - len);
-			if (strcmp(c, r) == 0) {
-				t->sz -= len + 1;
-				memmove(c, c + len + 1, t->sz - (c - b));
-				append = 1;
-				continue;
-			}
-		}
-		c += len + 1;
-	}
-
-	while (t->sz + slen + 1 >= t->cap) {
-		t->cap *= 2;
-		if ((t->buf = realloc(t->buf, t->cap)) == NULL)
-			err(EXIT_FAILURE, "realloc failed");
-	}
-	b = t->buf;
-	strncpy(&b[t->sz], s, slen);
-	b[t->sz + slen] = '\0';
-	t->sz += slen + 1;
-}
-
-static int
-lookup_string(struct section *t, const char *s)
-{
-	const char	*b, *c, *r;
-	size_t		 len, slen;
-
-	slen = strlen(s);
-	b = t->buf;
-	for (c = b; c < b + t->sz;) {
-		len = strlen(c);
-		if (len >= slen) {
-			r = c + (len - slen);
-			if (strcmp(r, s) == 0)
-				return (r - b);
-		}
-		c += len + 1;
-	}
-
-	return (-1);
-}
-
 static uint32_t crctable[256] =
 {
 	0x00000000L, 0x77073096L, 0xEE0E612CL, 0x990951BAL,