diff --git a/skeletons/OCTET_STRING.c b/skeletons/OCTET_STRING.c
index 63fbcc1..bdf9b85 100644
--- a/skeletons/OCTET_STRING.c
+++ b/skeletons/OCTET_STRING.c
@@ -1862,6 +1862,66 @@
     }
 }
 
+
+size_t
+OCTET_STRING_random_length_constrained(
+    const asn_TYPE_descriptor_t *td,
+    const asn_encoding_constraints_t *constraints, size_t max_length) {
+    const unsigned lengths[] = {0,     1,     2,     3,     4,     8,
+                                126,   127,   128,   16383, 16384, 16385,
+                                65534, 65535, 65536, 65537};
+    size_t rnd_len;
+
+    /* Figure out how far we should go */
+    rnd_len = lengths[asn_random_between(
+        0, sizeof(lengths) / sizeof(lengths[0]) - 1)];
+
+    if(!constraints) constraints = &td->encoding_constraints;
+    if(constraints->per_constraints) {
+        const asn_per_constraint_t *pc =
+            &td->encoding_constraints.per_constraints->size;
+        if(pc->flags & APC_CONSTRAINED) {
+            long suggested_upper_bound = pc->upper_bound < (ssize_t)max_length
+                                             ? pc->upper_bound
+                                             : max_length;
+            if(max_length <= (size_t)pc->lower_bound) {
+                return pc->lower_bound;
+            }
+            if(pc->flags & APC_EXTENSIBLE) {
+                switch(asn_random_between(0, 5)) {
+                case 0:
+                    if(pc->lower_bound > 0) {
+                        rnd_len = pc->lower_bound - 1;
+                        break;
+                    }
+                    /* Fall through */
+                case 1:
+                    rnd_len = pc->upper_bound + 1;
+                    break;
+                case 2:
+                    /* Keep rnd_len from the table */
+                    if(rnd_len <= max_length) {
+                        break;
+                    }
+                    /* Fall through */
+                default:
+                    rnd_len = asn_random_between(pc->lower_bound,
+                                                 suggested_upper_bound);
+                }
+            } else {
+                rnd_len =
+                    asn_random_between(pc->lower_bound, suggested_upper_bound);
+            }
+        } else {
+            rnd_len = asn_random_between(0, max_length);
+        }
+    } else if(rnd_len > max_length) {
+        rnd_len = asn_random_between(0, max_length);
+    }
+
+    return rnd_len;
+}
+
 asn_random_fill_result_t
 OCTET_STRING_random_fill(const asn_TYPE_descriptor_t *td, void **sptr,
                          const asn_encoding_constraints_t *constraints,
@@ -1872,9 +1932,6 @@
     asn_random_fill_result_t result_ok = {ARFILL_OK, 1};
     asn_random_fill_result_t result_failed = {ARFILL_FAILED, 0};
     asn_random_fill_result_t result_skipped = {ARFILL_SKIPPED, 0};
-    static unsigned lengths[] = {0,     1,     2,     3,     4,     8,
-                                 126,   127,   128,   16383, 16384, 16385,
-                                 65534, 65535, 65536, 65537};
     unsigned int unit_bytes = 1;
     unsigned long clb = 0;  /* Lower bound on char */
     unsigned long cub = 255;  /* Higher bound on char value */
@@ -1884,7 +1941,7 @@
     size_t rnd_len;
     OCTET_STRING_t *st;
 
-    if(max_length == 0) return result_skipped;
+    if(max_length == 0 && !*sptr) return result_skipped;
 
     switch(specs->subvariant) {
     default:
@@ -1922,50 +1979,8 @@
         }
     }
 
-    /* Figure out how far we should go */
-    rnd_len = lengths[asn_random_between(
-        0, sizeof(lengths) / sizeof(lengths[0]) - 1)];
-    if(constraints->per_constraints) {
-        const asn_per_constraint_t *pc =
-            &td->encoding_constraints.per_constraints->size;
-        if(pc->flags & APC_CONSTRAINED) {
-            long suggested_upper_bound = pc->upper_bound < (ssize_t)max_length
-                                             ? pc->upper_bound
-                                             : max_length;
-            if(max_length < (size_t)pc->lower_bound) {
-                return result_skipped;
-            }
-            if(pc->flags & APC_EXTENSIBLE) {
-                switch(asn_random_between(0, 5)) {
-                case 0:
-                    if(pc->lower_bound > 0) {
-                        rnd_len = pc->lower_bound - 1;
-                        break;
-                    }
-                    /* Fall through */
-                case 1:
-                    rnd_len = pc->upper_bound + 1;
-                    break;
-                case 2:
-                    /* Keep rnd_len from the table */
-                    if(rnd_len < max_length) {
-                        break;
-                    }
-                    /* Fall through */
-                default:
-                    rnd_len = asn_random_between(pc->lower_bound,
-                                                 suggested_upper_bound);
-                }
-            } else {
-                rnd_len =
-                    asn_random_between(pc->lower_bound, suggested_upper_bound);
-            }
-        } else {
-            rnd_len = asn_random_between(0, max_length - 1);
-        }
-    } else if(rnd_len >= max_length) {
-        rnd_len = asn_random_between(0, max_length - 1);
-    }
+    rnd_len =
+        OCTET_STRING_random_length_constrained(td, constraints, max_length);
 
     buf = CALLOC(unit_bytes, rnd_len + 1);
     if(!buf) return result_failed;
diff --git a/skeletons/OCTET_STRING.h b/skeletons/OCTET_STRING.h
index cbd1def..36b982d 100644
--- a/skeletons/OCTET_STRING.h
+++ b/skeletons/OCTET_STRING.h
@@ -89,6 +89,10 @@
 
 extern asn_OCTET_STRING_specifics_t asn_SPC_OCTET_STRING_specs;
 
+size_t OCTET_STRING_random_length_constrained(
+    const asn_TYPE_descriptor_t *, const asn_encoding_constraints_t *,
+    size_t max_length);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/skeletons/UTF8String.c b/skeletons/UTF8String.c
index 7d7cd8b..ae48063 100644
--- a/skeletons/UTF8String.c
+++ b/skeletons/UTF8String.c
@@ -203,22 +203,21 @@
 /*
  * Biased function for randomizing UTF-8 sequences.
  */
-static uint32_t
+static size_t
 UTF8String__random_char(uint8_t *b, size_t size) {
-    struct rnd_value {
+    static const struct rnd_value {
         const char *value;
         size_t size;
-    };
-    static const struct rnd_value values[] = {{"\0", 1},
-                                              {"\x01", 1},
-                                              {"\x7f", 1},
-                                              {"\xc2\xa2", 2},
-                                              {"\xe2\x82\xac", 3},
-                                              {"\xf0\x90\x8d\x88", 4},
-                                              {"\xf4\x8f\xbf\xbf", 4}};
+    } values[] = {{"\0", 1},
+                  {"\x01", 1},
+                  {"\x7f", 1},
+                  {"\xc2\xa2", 2},
+                  {"\xe2\x82\xac", 3},
+                  {"\xf0\x90\x8d\x88", 4},
+                  {"\xf4\x8f\xbf\xbf", 4}};
 
     const struct rnd_value *v;
-    size_t max_idx;
+    size_t max_idx = 0;
 
     switch(size) {
     case 0:
@@ -230,8 +229,10 @@
     case 2:
         max_idx = 3;
         break;
+    default:
     case 4:
-        return sizeof(values) / sizeof(values[0]) - 1;
+        max_idx = sizeof(values) / sizeof(values[0]) - 1;
+        break;
     }
 
     v = &values[asn_random_between(0, max_idx)];
@@ -246,9 +247,6 @@
     asn_random_fill_result_t result_ok = {ARFILL_OK, 1};
     asn_random_fill_result_t result_failed = {ARFILL_FAILED, 0};
     asn_random_fill_result_t result_skipped = {ARFILL_SKIPPED, 0};
-    static unsigned lengths[] = {0,     1,     2,     3,     4,     8,
-                                 126,   127,   128,   16383, 16384, 16385,
-                                 65534, 65535, 65536, 65537};
     uint8_t *buf;
     uint8_t *bend;
     uint8_t *b;
@@ -256,17 +254,11 @@
     size_t idx;
     UTF8String_t *st;
 
-    (void)td;
-    (void)constraints;
-
-    if(max_length == 0) return result_skipped;
+    if(max_length == 0 && !*sptr) return result_skipped;
 
     /* Figure out how far we should go */
-    rnd_len = lengths[asn_random_between(
-        0, sizeof(lengths) / sizeof(lengths[0]) - 1)];
-    if(4 * rnd_len >= max_length) {
-        rnd_len = asn_random_between(0, (max_length - 1) / 4);
-    }
+    rnd_len = OCTET_STRING_random_length_constrained(td, constraints,
+                                                     max_length / 4);
 
     buf = CALLOC(4, rnd_len + 1);
     if(!buf) return result_failed;
@@ -288,10 +280,11 @@
             return result_failed;
         }
     }
-    assert(UTF8String_length(st) == (ssize_t)rnd_len);
 
     st->buf = buf;
     st->size = b - buf;
 
+    assert(UTF8String_length(st) == (ssize_t)rnd_len);
+
     return result_ok;
 }
diff --git a/tests/tests-randomized/Makefile.am b/tests/tests-randomized/Makefile.am
index a02982b..605b64f 100644
--- a/tests/tests-randomized/Makefile.am
+++ b/tests/tests-randomized/Makefile.am
@@ -33,6 +33,7 @@
 TESTS += bundles/07-VisibleString-bundle.txt
 TESTS += bundles/08-OBJECT-IDENTIFIER-bundle.txt
 TESTS += bundles/09-RELATIVE-OID-bundle.txt
+TESTS += bundles/10-UTF8String-bundle.txt
 
 EXTRA_DIST =                    \
     random-test-driver.c        \
diff --git a/tests/tests-randomized/bundles/10-UTF8String-bundle.txt b/tests/tests-randomized/bundles/10-UTF8String-bundle.txt
new file mode 100644
index 0000000..b2581e9
--- /dev/null
+++ b/tests/tests-randomized/bundles/10-UTF8String-bundle.txt
@@ -0,0 +1,4 @@
+UTF8String
+UTF8String (SIZE(3))
+UTF8String (FROM("A".."Z"))
+UTF8String (FROM("A".."Z") INTERSECTION SIZE(3))