diff --git a/src/cmdhist.c b/src/cmdhist.c
index 684c08e..74089b2 100644
--- a/src/cmdhist.c
+++ b/src/cmdhist.c
@@ -125,8 +125,6 @@
 {
     int		newlen;	    // new length of history table
     histentry_T	*temp;
-    int		i;
-    int		j;
     int		type;
 
     // If size of history table changed, reallocate it
@@ -159,11 +157,16 @@
 
 	if (hisidx[type] < 0)		// there are no entries yet
 	{
+	    int	i;
+
 	    for (i = 0; i < newlen; ++i)
 		clear_hist_entry(&temp[i]);
 	}
 	else if (newlen > hislen)	// array becomes bigger
 	{
+	    int	i;
+	    int	j;
+
 	    for (i = 0; i <= hisidx[type]; ++i)
 		temp[i] = history[type][i];
 	    j = i;
@@ -174,13 +177,19 @@
 	}
 	else				// array becomes smaller or 0
 	{
+	    int	i;
+	    int	j;
+
 	    j = hisidx[type];
 	    for (i = newlen - 1; ; --i)
 	    {
 		if (i >= 0)		// copy newest entries
 		    temp[i] = history[type][j];
 		else			// remove older entries
+		{
 		    vim_free(history[type][j].hisstr);
+		    history[type][j].hisstrlen = 0;
+		}
 		if (--j < 0)
 		    j = hislen - 1;
 		if (j == hisidx[type])
@@ -200,6 +209,7 @@
     hisptr->hisnum = 0;
     hisptr->viminfo = FALSE;
     hisptr->hisstr = NULL;
+    hisptr->hisstrlen = 0;
     hisptr->time_set = 0;
 }
 
@@ -218,6 +228,7 @@
     int	    i;
     int	    last_i = -1;
     char_u  *p;
+    size_t  len;
 
     if (hisidx[type] < 0)
 	return FALSE;
@@ -232,7 +243,7 @@
 	p = history[type][i].hisstr;
 	if (STRCMP(str, p) == 0
 		&& !(writing && history[type][i].viminfo)
-		&& (type != HIST_SEARCH || sep == p[STRLEN(p) + 1]))
+		&& (type != HIST_SEARCH || sep == p[history[type][i].hisstrlen + 1]))
 	{
 	    if (!move_to_front)
 		return TRUE;
@@ -247,6 +258,7 @@
 	return FALSE;
 
     str = history[type][i].hisstr;
+    len = history[type][i].hisstrlen;
     while (i != hisidx[type])
     {
 	if (++i >= hislen)
@@ -257,6 +269,7 @@
     history[type][i].hisnum = ++hisnum[type];
     history[type][i].viminfo = FALSE;
     history[type][i].hisstr = str;
+    history[type][i].hisstrlen = len;
     history[type][i].time_set = vim_time();
     return TRUE;
 }
@@ -337,8 +350,13 @@
 
     // Store the separator after the NUL of the string.
     hisptr->hisstr = vim_strnsave(new_entry, new_entrylen + 2);
-    if (hisptr->hisstr != NULL)
+    if (hisptr->hisstr == NULL)
+	hisptr->hisstrlen = 0;
+    else
+    {
 	hisptr->hisstr[new_entrylen + 1] = sep;
+	hisptr->hisstrlen = new_entrylen;
+    }
 
     hisptr->hisnum = ++hisnum[histype];
     hisptr->viminfo = FALSE;
@@ -406,20 +424,6 @@
 }
 
 /*
- * Get a history entry by its index.
- * "histype" may be one of the HIST_ values.
- */
-    static char_u *
-get_history_entry(int histype, int idx)
-{
-    idx = calc_hist_idx(histype, idx);
-    if (idx >= 0)
-	return history[histype][idx].hisstr;
-    else
-	return (char_u *)"";
-}
-
-/*
  * Clear all entries of a history.
  * "histype" may be one of the HIST_ values.
  */
@@ -517,6 +521,7 @@
 	return FALSE;
     idx = hisidx[histype];
     vim_free(history[histype][i].hisstr);
+    history[histype][i].hisstrlen = 0;
 
     // When deleting the last added search string in a mapping, reset
     // last_maptick, so that the last added search string isn't deleted again.
@@ -576,7 +581,6 @@
 f_histdel(typval_T *argvars UNUSED, typval_T *rettv UNUSED)
 {
     int		n;
-    char_u	buf[NUMBUFLEN];
     char_u	*str;
 
     if (in_vim9script()
@@ -595,9 +599,14 @@
 	n = del_history_idx(get_histtype(str),
 					  (int)tv_get_number(&argvars[1]));
     else
+    {
+	char_u	buf[NUMBUFLEN];
+
 	// string given: remove all matching entries
 	n = del_history_entry(get_histtype(str),
 				      tv_get_string_buf(&argvars[1], buf));
+    }
+
     rettv->vval.v_number = n;
 }
 
@@ -607,9 +616,7 @@
     void
 f_histget(typval_T *argvars UNUSED, typval_T *rettv)
 {
-    int		type;
-    int		idx;
-    char_u	*str;
+    char_u  *str;
 
     if (in_vim9script()
 	    && (check_for_string_arg(argvars, 0) == FAIL
@@ -621,13 +628,21 @@
 	rettv->vval.v_string = NULL;
     else
     {
+	int type;
+	int idx;
+
 	type = get_histtype(str);
 	if (argvars[1].v_type == VAR_UNKNOWN)
 	    idx = get_history_idx(type);
 	else
 	    idx = (int)tv_get_number_chk(&argvars[1], NULL);
 						    // -1 on type error
-	rettv->vval.v_string = vim_strsave(get_history_entry(type, idx));
+
+	idx = calc_hist_idx(type, idx);
+	if (idx < 0)
+	    rettv->vval.v_string = vim_strnsave((char_u *)"", 0);
+	else
+	    rettv->vval.v_string = vim_strnsave(history[type][idx].hisstr, history[type][idx].hisstrlen);
     }
     rettv->v_type = VAR_STRING;
 }
@@ -647,10 +662,9 @@
     histname = tv_get_string_chk(&argvars[0]);
     i = histname == NULL ? HIST_CMD - 1 : get_histtype(histname);
     if (i >= HIST_CMD && i < HIST_COUNT)
-	i = get_history_idx(i);
+	rettv->vval.v_number = get_history_idx(i);
     else
-	i = -1;
-    rettv->vval.v_number = i;
+	rettv->vval.v_number = -1;
 }
 #endif // FEAT_EVAL
 
@@ -662,17 +676,21 @@
     void
 remove_key_from_history(void)
 {
+    char_u	*p_start;
+    char_u	*p_end;
     char_u	*p;
     int		i;
 
     i = hisidx[HIST_CMD];
     if (i < 0)
 	return;
-    p = history[HIST_CMD][i].hisstr;
-    if (p == NULL)
+    p_start = history[HIST_CMD][i].hisstr;
+    if (p_start == NULL)
 	return;
 
-    for ( ; *p; ++p)
+    p_end = p_start + history[HIST_CMD][i].hisstrlen;
+    for (p = p_start; *p; ++p)
+    {
 	if (STRNCMP(p, "key", 3) == 0 && !SAFE_isalpha(p[3]))
 	{
 	    p = vim_strchr(p + 3, '=');
@@ -682,9 +700,14 @@
 	    for (i = 0; p[i] && !VIM_ISWHITE(p[i]); ++i)
 		if (p[i] == '\\' && p[i + 1])
 		    ++i;
-	    STRMOVE(p, p + i);
+
+	    mch_memmove(p, p + i, (p_end - (p + i)) + 1);	    // +1 for the NUL
+	    p_end -= i;						    // adjust p_end for shortened string
 	    --p;
 	}
+    }
+
+    history[HIST_CMD][i].hisstrlen = (size_t)(p_end - p_start);
 }
 #endif
 
@@ -750,17 +773,16 @@
 
     for (; !got_int && histype1 <= histype2; ++histype1)
     {
-	STRCPY(IObuff, "\n      #  ");
-	STRCAT(STRCAT(IObuff, history_names[histype1]), " history");
+	vim_snprintf((char *)IObuff, IOSIZE, "\n      #  %s history", history_names[histype1]);
 	msg_puts_title((char *)IObuff);
 	idx = hisidx[histype1];
 	hist = history[histype1];
 	j = hisidx1;
 	k = hisidx2;
 	if (j < 0)
-	    j = (-j > hislen) ? 0 : hist[(hislen+j+idx+1) % hislen].hisnum;
+	    j = (-j > hislen) ? 0 : hist[(hislen + j + idx + 1) % hislen].hisnum;
 	if (k < 0)
-	    k = (-k > hislen) ? 0 : hist[(hislen+k+idx+1) % hislen].hisnum;
+	    k = (-k > hislen) ? 0 : hist[(hislen + k + idx + 1) % hislen].hisnum;
 	if (idx >= 0 && j <= k)
 	    for (i = idx + 1; !got_int; ++i)
 	    {
@@ -770,14 +792,16 @@
 			&& hist[i].hisnum >= j && hist[i].hisnum <= k
 			&& !message_filtered(hist[i].hisstr))
 		{
+		    int  len;
+
 		    msg_putchar('\n');
-		    sprintf((char *)IObuff, "%c%6d  ", i == idx ? '>' : ' ',
-							      hist[i].hisnum);
+		    len = vim_snprintf((char *)IObuff, IOSIZE,
+				"%c%6d  ", i == idx ? '>' : ' ', hist[i].hisnum);
 		    if (vim_strsize(hist[i].hisstr) > (int)Columns - 10)
-			trunc_string(hist[i].hisstr, IObuff + STRLEN(IObuff),
-			     (int)Columns - 10, IOSIZE - (int)STRLEN(IObuff));
+			trunc_string(hist[i].hisstr, IObuff + len,
+			     (int)Columns - 10, IOSIZE - (int)len);
 		    else
-			STRCAT(IObuff, hist[i].hisstr);
+			STRCPY(IObuff + len, hist[i].hisstr);
 		    msg_outtrans(IObuff);
 		    out_flush();
 		}
diff --git a/src/ex_cmds.c b/src/ex_cmds.c
index b990de4..462232f 100644
--- a/src/ex_cmds.c
+++ b/src/ex_cmds.c
@@ -5192,10 +5192,10 @@
 	delim = *cmd;		// get the delimiter
 	++cmd;			// skip delimiter if there is one
 	pat = cmd;		// remember start of pattern
-	patlen = STRLEN(pat);
 	cmd = skip_regexp_ex(cmd, delim, magic_isset(), &eap->arg, NULL, NULL);
 	if (cmd[0] == delim)		    // end delimiter found
 	    *cmd++ = NUL;		    // replace it with a NUL
+	patlen = STRLEN(pat);
     }
 
     if (search_regcomp(pat, patlen, &used_pat, RE_BOTH, which_pat, SEARCH_HIS,
diff --git a/src/ex_getln.c b/src/ex_getln.c
index b7804d1..60e9641 100644
--- a/src/ex_getln.c
+++ b/src/ex_getln.c
@@ -1430,7 +1430,7 @@
 	else
 	{
 	    p = get_histentry(histype)[hiscnt].hisstr;
-	    plen = STRLEN(p);
+	    plen = get_histentry(histype)[hiscnt].hisstrlen;
 	}
 
 	if (histype == HIST_SEARCH
diff --git a/src/structs.h b/src/structs.h
index da403ff..e4a79f5 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -1283,6 +1283,7 @@
     int		hisnum;		// identifying number
     int		viminfo;	// when TRUE hisstr comes from viminfo
     char_u	*hisstr;	// actual entry, separator char after the NUL
+    size_t	hisstrlen;	// length of hisstr (excluding the NUL)
     time_t	time_set;	// when it was typed, zero if unknown
 } histentry_T;
 
diff --git a/src/version.c b/src/version.c
index cd49f58..d09faf2 100644
--- a/src/version.c
+++ b/src/version.c
@@ -705,6 +705,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    798,
+/**/
     797,
 /**/
     796,
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;