diff --git a/src/viminfo.c b/src/viminfo.c
index 11a2946..2196d3c 100644
--- a/src/viminfo.c
+++ b/src/viminfo.c
@@ -552,25 +552,32 @@
 
     // Need to re-allocate to append the separator byte.
     len = STRLEN(val);
-    p = alloc(len + 2);
-    if (p == NULL)
-	goto done;
-
     if (type == HIST_SEARCH)
     {
+	p = alloc((size_t)len + 1);	    // +1 for the NUL. val already
+					    // includes the separator.
+	if (p == NULL)
+	    goto done;
+
 	// Search entry: Move the separator from the first
 	// column to after the NUL.
 	mch_memmove(p, val + 1, (size_t)len);
 	p[len] = sep;
+	--len;				    // take into account the shortened string
     }
     else
     {
+	p = alloc((size_t)len + 2);	    // +1 for NUL and +1 for separator
+	if (p == NULL)
+	    goto done;
+
 	// Not a search entry: No separator in the viminfo
 	// file, add a NUL separator.
-	mch_memmove(p, val, (size_t)len + 1);
-	p[len + 1] = NUL;
+	mch_memmove(p, val, (size_t)len + 1);	// +1 to include the NUL
+	p[len + 1] = NUL;			// put the separator *after* the string's NUL
     }
     viminfo_history[type][viminfo_hisidx[type]].hisstr = p;
+    viminfo_history[type][viminfo_hisidx[type]].hisstrlen = (size_t)len;
     viminfo_history[type][viminfo_hisidx[type]].time_set = 0;
     viminfo_history[type][viminfo_hisidx[type]].viminfo = TRUE;
     viminfo_history[type][viminfo_hisidx[type]].hisnum = 0;
@@ -629,8 +636,9 @@
     for (idx = 0; idx < viminfo_hisidx[type]; ++idx)
     {
 	p = viminfo_history[type][idx].hisstr;
+	len = viminfo_history[type][idx].hisstrlen;
 	if (STRCMP(val, p) == 0
-		&& (type != HIST_SEARCH || sep == p[STRLEN(p) + 1]))
+		&& (type != HIST_SEARCH || sep == p[len + 1]))
 	{
 	    overwrite = TRUE;
 	    break;
@@ -654,6 +662,7 @@
 	    // Put the separator after the NUL.
 	    p[len + 1] = sep;
 	    viminfo_history[type][idx].hisstr = p;
+	    viminfo_history[type][idx].hisstrlen = (size_t)len;
 	    viminfo_history[type][idx].hisnum = 0;
 	    viminfo_history[type][idx].viminfo = TRUE;
 	    viminfo_hisidx[type]++;
@@ -699,6 +708,7 @@
     {
 	vim_free(histentry[idx].hisstr);
 	histentry[idx].hisstr = viminfo_history[type][i].hisstr;
+	histentry[idx].hisstrlen = viminfo_history[type][i].hisstrlen;
 	histentry[idx].viminfo = TRUE;
 	histentry[idx].time_set = viminfo_history[type][i].time_set;
 	if (--idx < 0)
@@ -768,6 +778,7 @@
 	{
 	    new_hist[i] = *tot_hist[i];
 	    tot_hist[i]->hisstr = NULL;
+	    tot_hist[i]->hisstrlen = 0;
 	    if (new_hist[i].hisnum == 0)
 		new_hist[i].hisnum = ++*hisnum;
 	}
@@ -778,9 +789,15 @@
 
     // Free what is not kept.
     for (i = 0; i < viminfo_hisidx[type]; i++)
+    {
 	vim_free(viminfo_history[type][i].hisstr);
+	viminfo_history[type][i].hisstrlen = 0;
+    }
     for (i = 0; i < hislen; i++)
+    {
 	vim_free(histentry[i].hisstr);
+	histentry[i].hisstrlen = 0;
+    }
     vim_free(histentry);
     set_histentry(type, new_hist);
     vim_free(tot_hist);
@@ -867,20 +884,30 @@
 			&& !(round == 2 && i >= viminfo_hisidx[type]))
 		{
 		    char_u  *p;
+		    size_t  plen;
 		    time_t  timestamp;
 		    int	    c = NUL;
 
 		    if (round == 1)
 		    {
 			p = histentry[i].hisstr;
+			plen = histentry[i].hisstrlen;
 			timestamp = histentry[i].time_set;
 		    }
 		    else
 		    {
-			p = viminfo_history[type] == NULL ? NULL
-					    : viminfo_history[type][i].hisstr;
-			timestamp = viminfo_history[type] == NULL ? 0
-					  : viminfo_history[type][i].time_set;
+			if (viminfo_history[type] == NULL)
+			{
+			    p = NULL;
+			    plen = 0;
+			    timestamp = 0;
+			}
+			else
+			{
+			    p = viminfo_history[type][i].hisstr;
+			    plen = viminfo_history[type][i].hisstrlen;
+			    timestamp = viminfo_history[type][i].time_set;
+			}
 		    }
 
 		    if (p != NULL && (round == 2
@@ -893,7 +920,7 @@
 			// second column; use a space if there isn't one.
 			if (type == HIST_SEARCH)
 			{
-			    c = p[STRLEN(p) + 1];
+			    c = p[plen + 1];
 			    putc(c == NUL ? ' ' : c, fp);
 			}
 			viminfo_writestring(fp, p);
@@ -931,7 +958,10 @@
 	}
 	for (i = 0; i < viminfo_hisidx[type]; ++i)
 	    if (viminfo_history[type] != NULL)
+	    {
 		vim_free(viminfo_history[type][i].hisstr);
+		viminfo_history[type][i].hisstrlen = 0;
+	    }
 	VIM_CLEAR(viminfo_history[type]);
 	viminfo_hisidx[type] = 0;
     }
@@ -1112,6 +1142,7 @@
 			// freed later, also need to free "buf" later
 			value->bv_tofree = buf;
 		    s = sconv;
+		    len = STRLEN(s);
 		    converted = TRUE;
 		}
 	    }
@@ -1119,7 +1150,7 @@
 	    // Need to copy in allocated memory if the string wasn't allocated
 	    // above and we did allocate before, thus vir_line may change.
 	    if (s != buf && allocated && !converted)
-		s = vim_strsave(s);
+		s = vim_strnsave(s, len);
 	    value->bv_string = s;
 	    value->bv_type = BVAL_STRING;
 	    value->bv_len = len;