Repository: ParkMyCar/compact_str
Pull request #160 (2022-07-17 19:32:27)

perf: Implement realloc for BoxString
This PR implements `realloc(size)` for `BoxString`, which is the underlying heap representation of a `CompactString`


Patch:
diff --git a/.github/ISSUE_TEMPLATE.md b/.github/ISSUE_TEMPLATE.md
new file mode 100644
index 00000000..465d6fe4
--- /dev/null
+++ b/.github/ISSUE_TEMPLATE.md
@@ -0,0 +1,8 @@
+---
+title: Fuzz Failure! {{ env.GITHUB_RUN_ID }}
+assignees: ParkMyCar
+labels: bug, fuzz
+---
+There was a failing test case found when fuzzing!
+
+See [Action Run {{ env.GITHUB_RUN_ID }}](https://github.com/ParkMyCar/compact_str/actions/runs/{{ env.GITHUB_RUN_ID }})
diff --git a/.github/workflows/fuzz.yml b/.github/workflows/fuzz.yml
index 4d3a6054..e350ec99 100644
--- a/.github/workflows/fuzz.yml
+++ b/.github/workflows/fuzz.yml
@@ -60,6 +60,13 @@ jobs:
         with:
           command: fuzz
           args: run --features=libfuzzer-sys --debug-assertions compact_str -- -max_total_time=${{ env.fuzz_time }}
+      - name: File Issue (if failure found)
+        if: failure()
+        uses: JasonEtco/create-an-issue@v2.6
+        env:
+          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
+        with:
+          update_existing: true
 
   honggfuzz_x86_64:
     name: honggfuzz [x86_64]
@@ -89,6 +96,13 @@ jobs:
         with:
           command: hfuzz
           args: run honggfuzz
+      - name: File Issue (if failure found)
+        if: failure()
+        uses: JasonEtco/create-an-issue@v2.6
+        env:
+          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
+        with:
+          update_existing: true
 
   afl_x86_64:
     name: AFL++ [x86_64]
@@ -153,6 +167,13 @@ jobs:
         with:
           name: Upload Crashes
           path: ./fuzz/afl/out/default/crashes/
+      - name: File Issue (if failure found)
+        if: failure()
+        uses: JasonEtco/create-an-issue@v2.6
+        env:
+          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
+        with:
+          update_existing: true
 
   afl_armv7:
     name: AFL++ [ARMv7]
@@ -200,3 +221,10 @@ jobs:
         with:
           name: Upload Crashes
           path: ./fuzz/afl/out/default/crashes/
+      - name: File Issue (if failure found)
+        if: failure()
+        uses: JasonEtco/create-an-issue@v2.6
+        env:
+          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
+        with:
+          update_existing: true
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 5e4dbd57..9004244f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,7 +1,39 @@
 # Upcoming
+* impl `AddAssign` (`+=`) for `CompactString`
+    * Implemented in [`add AddAssign operator`](https://github.com/ParkMyCar/compact_str/pull/159)
+* Implement [`markup::Render`](https://docs.rs/markup/latest/markup/trait.Render.html) trait
+    * Implemented in [`#157 Implement markup::Render trait and document features`](https://github.com/ParkMyCar/compact_str/pull/157)
+* Add `split_off()` method
+    * Implemented in [`#154 Implement split_off()`](https://github.com/ParkMyCar/compact_str/pull/154)
+* Add `drain()` method
+    * Implemented in [`#153 Implement drain()`](https://github.com/ParkMyCar/compact_str/pull/153)
+* Add `clear()` method
+    * Implemented in [`#149 Implement clear()`](https://github.com/ParkMyCar/compact_str/pull/149)
+* Add `insert()` and `insert_str()` methods
+    * Implemented in [`#148 Implement insert() and insert_str()`](https://github.com/ParkMyCar/compact_str/pull/148)
+* Implement the `Arbitrary` trait from [`arbitrary`](https://docs.rs/arbitrary/latest/arbitrary/), [`proptest`](https://docs.rs/proptest/latest/proptest/), and [`quickcheck`](https://docs.rs/quickcheck/latest/quickcheck/)
+    * Implemented in [`146 feat: Implemented the Arbitrary trait from various crate`](https://github.com/ParkMyCar/compact_str/pull/146)
+* Add `truncate()` method
+    * Implemented in [`#132 Implement truncate()`](https://github.com/ParkMyCar/compact_str/pull/132)
+* Add `replace_range()` method
+    * Implemented in [`#125 Implement replace_range()`](https://github.com/ParkMyCar/compact_str/pull/125)
+* Add `as_mut_str()` method
+    * Implemented in [`#124 Add as_mut_str() method`](https://github.com/ParkMyCar/compact_str/pull/124)
 * Implemented `From<CompactString>` for `String`
     * Implemented in [`#118 feat: add impl From<CompactString> for String`](https://github.com/ParkMyCar/compact_str/pull/118)
 
+# 0.5.2
+### July 24, 2022
+* Fix error when creating `CompactString` with capacity `16711422` on 32-bit archiectures
+    * Implemented in [`#161 fix: Test case discovered by AFL`](https://github.com/ParkMyCar/compact_str/pull/161) 
+    * Backported in [`#167 backport(v0.5): Test case discovered by AFL`](https://github.com/ParkMyCar/compact_str/pull/167)
+
+# 0.5.1
+### June 27, 2022
+* Fix error when importing `compact_str` by change the existing Add<...> impls
+    * Implemented in [`#103 fix/feat: Change the existing Add<...> impls`](https://github.com/ParkMyCar/compact_str/pull/103)
+    * Backported
+
 # 0.5.0
 ### June 18, 2022
 * Add examples for `CompactStringExt` and `ToCompactString` traits, and `format_compact!(...)` macro
@@ -23,6 +55,12 @@
 * Add `format_compact!` macro
     * Implemented in [`#101 Add macro_rules format_compact!`](https://github.com/ParkMyCar/compact_str/pull/101)
 
+# 0.4.1
+### June 27, 2022
+* Fix error when importing `compact_str` by change the existing Add<...> impls
+    * Implemented in [`#103 fix/feat: Change the existing Add<...> impls`](https://github.com/ParkMyCar/compact_str/pull/103)
+    * Backported
+
 # 0.4.0
 ### May 27, 2022
 * Rename `CompactStr` -> `CompactString` and `ToCompactStr` -> `ToComapctString`
diff --git a/compact_str/Cargo.toml b/compact_str/Cargo.toml
index bd6df039..4208a597 100644
--- a/compact_str/Cargo.toml
+++ b/compact_str/Cargo.toml
@@ -24,6 +24,7 @@ itoa = "1"
 ryu = "1"
 
 [dev-dependencies]
+cfg-if = "1"
 proptest = { version = "1", default-features = false, features = ["std"] }
 quickcheck_macros = "1"
 rayon = "1"
diff --git a/compact_str/src/repr/boxed/capacity.rs b/compact_str/src/repr/boxed/capacity.rs
index 1dc00605..2ec3cbc3 100644
--- a/compact_str/src/repr/boxed/capacity.rs
+++ b/compact_str/src/repr/boxed/capacity.rs
@@ -2,8 +2,21 @@ use crate::repr::HEAP_MASK;
 
 // how many bytes a `usize` occupies
 const USIZE_SIZE: usize = core::mem::size_of::<usize>();
-// state that describes the capacity as being stored on the heap
-const CAPACITY_IS_ON_THE_HEAP: [u8; USIZE_SIZE] = [HEAP_MASK; USIZE_SIZE];
+
+/// Used to generate [`CAPACITY_IS_ON_THE_HEAP`]
+#[allow(non_snake_case)]
+const fn CAP_ON_HEAP_FLAG() -> [u8; USIZE_SIZE] {
+    // all bytes 255, with the last
+    let mut flag = [255; USIZE_SIZE];
+    flag[USIZE_SIZE - 1] = HEAP_MASK;
+    flag
+}
+
+/// State that describes the capacity as being stored on the heap.
+///
+/// All bytes `255`, with the last being [`HEAP_MASK`], using the same amount of bytes as `usize`
+/// Example (64-bit): `[255, 255, 255, 255, 255, 255, 255, 254]`
+const CAPACITY_IS_ON_THE_HEAP: [u8; USIZE_SIZE] = CAP_ON_HEAP_FLAG();
 
 // how many bytes we can use for capacity
 const SPACE_FOR_CAPACITY: usize = USIZE_SIZE - 1;
@@ -55,14 +68,6 @@ impl Capacity {
         }
     }
 
-    #[inline]
-    #[cfg(target_pointer_width = "64")]
-    pub const unsafe fn new_unchecked(capacity: usize) -> Self {
-        let mut bytes = capacity.to_le_bytes();
-        bytes[core::mem::size_of::<usize>() - 1] = HEAP_MASK;
-        Capacity { _buf: bytes }
-    }
-
     #[inline]
     pub fn as_usize(&self) -> Result<usize, ()> {
         if self._buf == CAPACITY_IS_ON_THE_HEAP {
@@ -81,19 +86,6 @@ impl Capacity {
     }
 
     #[inline(always)]
-    #[cfg(target_pointer_width = "64")]
-    pub unsafe fn as_usize_unchecked(&self) -> usize {
-        let mut usize_buf = [0u8; USIZE_SIZE];
-        core::ptr::copy_nonoverlapping(
-            self._buf.as_ptr(),
-            usize_buf.as_mut_ptr(),
-            SPACE_FOR_CAPACITY,
-        );
-        usize::from_le_bytes(usize_buf)
-    }
-
-    #[inline(always)]
-    #[cfg(not(target_pointer_width = "64"))]
     pub fn is_heap(&self) -> bool {
         self._buf == CAPACITY_IS_ON_THE_HEAP
     }
@@ -101,6 +93,8 @@ impl Capacity {
 
 #[cfg(test)]
 mod tests {
+    use rayon::prelude::*;
+
     use super::Capacity;
 
     #[test]
@@ -146,6 +140,27 @@ mod tests {
         let og = usize::MAX;
         assert!(Capacity::new(og).is_err());
     }
+
+    #[test]
+    #[cfg_attr(miri, ignore)]
+    fn test_all_valid_32bit_values() {
+        #[cfg(target_pointer_width = "32")]
+        assert_eq!(16_777_214, super::MAX_VALUE);
+
+        (0..=16_777_214)
+            .into_par_iter()
+            .for_each(|i| match Capacity::new(i) {
+                Ok(cap) => match cap.as_usize() {
+                    Ok(val) => assert_eq!(val, i, "value roundtriped to wrong value?"),
+                    Err(_) => panic!("value converted, but failed to roundtrip! val: {}", i),
+                },
+                Err(_) => panic!("failed to convert {}", i),
+            });
+
+        // one above the 32-bit max value
+        #[cfg(target_pointer_width = "32")]
+        assert!(Capacity::new(16_777_215).is_err());
+    }
 }
 
 crate::asserts::assert_size_eq!(Capacity, usize);
diff --git a/compact_str/src/repr/boxed/inner.rs b/compact_str/src/repr/boxed/inner.rs
index 27f012e5..ee4e8f0a 100644
--- a/compact_str/src/repr/boxed/inner.rs
+++ b/compact_str/src/repr/boxed/inner.rs
@@ -1,7 +1,6 @@
 const UNKNOWN: usize = 0;
 pub type StrBuffer = [u8; UNKNOWN];
 
-#[cfg(not(target_pointer_width = "64"))]
 pub mod heap_capacity {
     use core::ptr;
     use std::alloc;
@@ -37,7 +36,7 @@ pub mod heap_capacity {
         buffer: StrBuffer,
     }
 
-    fn layout(capacity: usize) -> alloc::Layout {
+    pub fn layout(capacity: usize) -> alloc::Layout {
         let buffer_layout = alloc::Layout::array::<u8>(capacity).expect("valid capacity");
         alloc::Layout::new::<BoxStringInnerHeapCapacity>()
             .extend(buffer_layout)
@@ -84,7 +83,7 @@ pub mod inline_capacity {
         buffer: StrBuffer,
     }
 
-    fn layout(capacity: usize) -> alloc::Layout {
+    pub fn layout(capacity: usize) -> alloc::Layout {
         let buffer_layout = alloc::Layout::array::<u8>(capacity).expect("valid capacity");
         alloc::Layout::new::<BoxStringInnerInlineCapacity>()
             .extend(buffer_layout)
diff --git a/compact_str/src/repr/boxed/mod.rs b/compact_str/src/repr/boxed/mod.rs
index f5f1fb73..40480a06 100644
--- a/compact_str/src/repr/boxed/mod.rs
+++ b/compact_str/src/repr/boxed/mod.rs
@@ -6,6 +6,8 @@ use core::{
     slice,
     str,
 };
+use std::alloc;
+use std::ptr::NonNull;
 
 mod capacity;
 use capacity::Capacity;
@@ -14,6 +16,19 @@ mod inner;
 
 const MIN_SIZE: usize = core::mem::size_of::<usize>() / 2;
 
+/// [`BoxString`] grows at an amortized rates of 1.5x
+///
+/// Note: this is different than [`std::string::String`], which grows at a rate of 2x. It's debated
+/// which is better, for now we'll stick with a rate of 1.5x
+///
+/// TODO: Handle overflows in the case of __very__ large Strings
+#[inline(always)]
+fn amortized_growth(cur_len: usize, additional: usize) -> usize {
+    let required = cur_len + additional;
+    let amortized = 3 * cur_len / 2;
+    core::cmp::max(amortized, required)
+}
+
 #[repr(C)]
 pub struct BoxString {
     ptr: ptr::NonNull<u8>,
@@ -38,23 +53,16 @@ impl BoxString {
         // to be at least size_of::<usize>, so we know it'll be non-zero.
         let (cap, ptr) = unsafe { BoxString::alloc_ptr(capacity) };
 
+        let write_ptr = if !cap.is_heap() {
+            ptr.as_ptr()
+        } else {
+            unsafe { ptr.as_ptr().add(core::mem::size_of::<usize>()) }
+        };
+
         // SAFETY: We know both `src` and `dest` are valid for respectively reads and writes of
         // length `len` because `len` comes from `src`, and `dest` was allocated to be at least that
         // length. We also know they're non-overlapping because `dest` is newly allocated
-        #[cfg(target_pointer_width = "64")]
-        unsafe {
-            ptr.as_ptr().copy_from_nonoverlapping(text.as_ptr(), len)
-        };
-
-        #[cfg(not(target_pointer_width = "64"))]
-        {
-            let write_ptr = if cap.is_heap() {
-                unsafe { ptr.as_ptr().add(core::mem::size_of::<usize>()) }
-            } else {
-                ptr.as_ptr()
-            };
-            unsafe { write_ptr.copy_from_nonoverlapping(text.as_ptr(), len) };
-        }
+        unsafe { write_ptr.copy_from_nonoverlapping(text.as_ptr(), len) };
 
         BoxString { len, ptr, cap }
     }
@@ -78,31 +86,25 @@ impl BoxString {
 
     #[inline(always)]
     unsafe fn alloc_ptr(capacity: usize) -> (Capacity, ptr::NonNull<u8>) {
-        #[cfg(target_pointer_width = "64")]
-        let (cap, ptr) = {
-            debug_assert!(capacity <= capacity::MAX_VALUE);
-
-            let cap = Capacity::new_unchecked(capacity);
-            let ptr = inner::inline_capacity::alloc(capacity);
+        #[cold]
+        unsafe fn alloc_ptr_heap(capacity: usize, cap: Capacity) -> (Capacity, ptr::NonNull<u8>) {
+            let ptr = inner::heap_capacity::alloc(capacity);
+            // write our capacity onto the heap
+            core::ptr::copy_nonoverlapping(
+                capacity.to_le_bytes().as_ptr(),
+                ptr.as_ptr(),
+                core::mem::size_of::<usize>(),
+            );
             (cap, ptr)
-        };
+        }
 
-        #[cfg(not(target_pointer_width = "64"))]
         let (cap, ptr) = match Capacity::new(capacity) {
             Ok(cap) => {
+                debug_assert!(capacity <= capacity::MAX_VALUE);
                 let ptr = inner::inline_capacity::alloc(capacity);
                 (cap, ptr)
             }
-            Err(cap) => {
-                let ptr = inner::heap_capacity::alloc(capacity);
-                // write our capacity onto the heap
-                core::ptr::copy_nonoverlapping(
-                    capacity.to_le_bytes().as_ptr(),
-                    ptr.as_ptr(),
-                    core::mem::size_of::<usize>(),
-                );
-                (cap, ptr)
-            }
+            Err(cap) => alloc_ptr_heap(capacity, cap),
         };
 
         (cap, ptr)
@@ -111,10 +113,7 @@ impl BoxString {
     #[inline]
     pub fn with_additional(text: &str, additional: usize) -> Self {
         let len = text.len();
-
-        let required = len + additional;
-        let amortized = 3 * len / 2;
-        let new_capacity = core::cmp::max(amortized, required);
+        let new_capacity = amortized_growth(len, additional);
 
         // TODO: Handle overflows in the case of __very__ large Strings
         debug_assert!(new_capacity >= len);
@@ -153,6 +152,11 @@ impl BoxString {
 
     #[inline]
     pub fn into_string(self) -> String {
+        #[cold]
+        fn into_string_heap(this: BoxString) -> String {
+            String::from(this.as_str())
+        }
+
         match self.cap.as_usize() {
             Ok(cap) => {
                 // Ensure that we don't free the data we are transferring the buffer to `String`
@@ -166,7 +170,7 @@ impl BoxString {
                 // * `BoxString` only ever contains valid UTF-8.
                 unsafe { String::from_raw_parts(this.ptr.as_ptr(), this.len, cap) }
             }
-            Err(_) => String::from(self.as_str()),
+            Err(_) => into_string_heap(self),
         }
     }
 
@@ -200,11 +204,15 @@ impl BoxString {
             return;
         }
 
-        // We need to reserve additional space, so create a new BoxString with additional space
-        let new = BoxString::with_additional(self.as_str(), additional);
+        let new_capacity = amortized_growth(len, additional);
 
-        // Set our new BoxString as self
-        *self = new;
+        // try to realloc, creating a new BoxString on failure
+        if self.realloc(new_capacity).is_err() {
+            // We failed to realloc, so create a new BoxString
+            let new = BoxString::with_additional(self.as_str(), additional);
+            // Set our new BoxString as self
+            *self = new;
+        }
     }
 
     #[inline]
@@ -214,31 +222,26 @@ impl BoxString {
 
     #[inline]
     pub fn capacity(&self) -> usize {
-        #[cfg(target_pointer_width = "64")]
-        {
-            debug_assert!(self.cap.as_usize().is_ok());
-            unsafe { self.cap.as_usize_unchecked() }
+        #[cold]
+        fn capacity_heap(this: &BoxString) -> usize {
+            let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
+            // copy bytes from the heap into our buffer
+            unsafe {
+                core::ptr::copy_nonoverlapping(
+                    this.ptr.as_ptr() as *const u8,
+                    usize_buf.as_mut_ptr(),
+                    core::mem::size_of::<usize>(),
+                );
+            };
+            // interpret those bytes as a usize
+            usize::from_le_bytes(usize_buf)
         }
-        #[cfg(not(target_pointer_width = "64"))]
-        {
-            match self.cap.as_usize() {
-                // capacity is on the stack, just return it!
-                Ok(cap) => cap,
-                // capacity is on the heap, we need to read it back
-                Err(_) => {
-                    let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
-                    // copy bytes from the heap into our buffer
-                    unsafe {
-                        core::ptr::copy_nonoverlapping(
-                            self.ptr.as_ptr() as *const u8,
-                            usize_buf.as_mut_ptr(),
-                            core::mem::size_of::<usize>(),
-                        );
-                    };
-                    // interpret those bytes as a usize
-                    usize::from_le_bytes(usize_buf)
-                }
-            }
+
+        match self.cap.as_usize() {
+            // capacity is on the stack, just return it!
+            Ok(cap) => cap,
+            // capacity is on the heap, we need to read it back
+            Err(_) => capacity_heap(self),
         }
     }
 
@@ -311,101 +314,154 @@ impl BoxString {
 
     #[inline]
     fn as_buffer(&self) -> &[u8] {
-        #[cfg(target_pointer_width = "64")]
-        {
-            debug_assert!(self.cap.as_usize().is_ok());
+        #[cold]
+        fn as_buffer_heap(this: &BoxString) -> &[u8] {
+            // read our first few bytes to get our capacity
+            let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
+            unsafe {
+                core::ptr::copy_nonoverlapping(
+                    this.ptr.as_ptr() as *const u8,
+                    usize_buf.as_mut_ptr(),
+                    core::mem::size_of::<usize>(),
+                );
+            };
+            let cap = usize::from_le_bytes(usize_buf);
 
+            // read `cap` bytes from our buffer, starting at an offset
+            let buf_start = unsafe { this.ptr.as_ptr().add(core::mem::size_of::<usize>()) };
             // SAFETY: Since we have an instance of `BoxStringInner` so we know the buffer is still
             // valid. Also since we're on a 64-bit arch, it's practically impossible for our
             // capacity to be stored on the heap
-            unsafe { slice::from_raw_parts(self.ptr.as_ptr(), self.cap.as_usize_unchecked()) }
+            unsafe { slice::from_raw_parts(buf_start, cap) }
         }
-        #[cfg(not(target_pointer_width = "64"))]
-        {
-            match self.cap.as_usize() {
-                // capacity is on the stack, so read the entire buffer!
-                Ok(cap) => unsafe { slice::from_raw_parts(self.ptr.as_ptr(), cap) },
-                // capacity is on the heap, we need to read the capacity, and then read the buffer
-                // starting from an offset
-                Err(_) => {
-                    // read our first few bytes to get our capacity
-                    let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
-                    unsafe {
-                        core::ptr::copy_nonoverlapping(
-                            self.ptr.as_ptr() as *const u8,
-                            usize_buf.as_mut_ptr(),
-                            core::mem::size_of::<usize>(),
-                        );
-                    };
-                    let cap = usize::from_le_bytes(usize_buf);
-
-                    // read `cap` bytes from our buffer, starting at an offset
-                    let buf_start = unsafe { self.ptr.as_ptr().add(core::mem::size_of::<usize>()) };
-                    unsafe { slice::from_raw_parts(buf_start, cap) }
-                }
-            }
+
+        match self.cap.as_usize() {
+            // capacity is on the stack, so read the entire buffer!
+            Ok(cap) => unsafe { slice::from_raw_parts(self.ptr.as_ptr(), cap) },
+            // capacity is on the heap, we need to read the capacity, and then read the buffer
+            // starting from an offset
+            Err(_) => as_buffer_heap(self),
         }
     }
 
     #[inline]
     unsafe fn as_mut_buffer(&mut self) -> &mut [u8] {
-        #[cfg(target_pointer_width = "64")]
-        {
-            debug_assert!(self.cap.as_usize().is_ok());
-
+        #[cold]
+        unsafe fn as_mut_buffer_heap(this: &mut BoxString) -> &mut [u8] {
+            // read our first few bytes to get our capacity
+            let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
+            core::ptr::copy_nonoverlapping(
+                this.ptr.as_ptr() as *const u8,
+                usize_buf.as_mut_ptr(),
+                core::mem::size_of::<usize>(),
+            );
+            let cap = usize::from_le_bytes(usize_buf);
+
+            // read `cap` bytes from our buffer, starting at an offset
+            let buf_start = this.ptr.as_ptr().add(core::mem::size_of::<usize>());
             // SAFETY: Since we have an instance of `BoxStringInner` so we know the buffer is still
             // valid. Also since we're on a 64-bit arch, it's practically impossible for our
             // capacity to be stored on the heap
-            slice::from_raw_parts_mut(self.ptr.as_ptr(), self.cap.as_usize_unchecked())
+            slice::from_raw_parts_mut(buf_start, cap)
         }
-        #[cfg(not(target_pointer_width = "64"))]
-        {
-            match self.cap.as_usize() {
-                // capacity is on the stack, so read the entire buffer!
-                Ok(cap) => slice::from_raw_parts_mut(self.ptr.as_ptr(), cap),
-                // capacity is on the heap, we need to read the capacity, and then read the buffer
-                // starting from an offset
-                Err(_) => {
-                    // read our first few bytes to get our capacity
-                    let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
-                    core::ptr::copy_nonoverlapping(
-                        self.ptr.as_ptr() as *const u8,
-                        usize_buf.as_mut_ptr(),
-                        core::mem::size_of::<usize>(),
-                    );
-                    let cap = usize::from_le_bytes(usize_buf);
 
-                    // read `cap` bytes from our buffer, starting at an offset
-                    let buf_start = self.ptr.as_ptr().add(core::mem::size_of::<usize>());
-                    slice::from_raw_parts_mut(buf_start, cap)
-                }
-            }
+        match self.cap.as_usize() {
+            // capacity is on the stack, so read the entire buffer!
+            Ok(cap) => slice::from_raw_parts_mut(self.ptr.as_ptr(), cap),
+            // capacity is on the heap, we need to read the capacity, and then read the buffer
+            // starting from an offset
+            Err(_) => as_mut_buffer_heap(self),
         }
     }
 
     #[inline(never)]
     unsafe fn drop_inner(&mut self) {
-        #[cfg(target_pointer_width = "64")]
-        {
-            inner::inline_capacity::dealloc(self.ptr, self.capacity())
+        #[cold]
+        unsafe fn drop_heap(this: &mut BoxString) {
+            // read our first few bytes to get our capacity
+            let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
+            core::ptr::copy_nonoverlapping(
+                this.ptr.as_ptr() as *const u8,
+                usize_buf.as_mut_ptr(),
+                core::mem::size_of::<usize>(),
+            );
+            let cap = usize::from_le_bytes(usize_buf);
+
+            inner::heap_capacity::dealloc(this.ptr, cap)
         }
 
-        #[cfg(not(target_pointer_width = "64"))]
         match self.cap.as_usize() {
             Ok(cap) => inner::inline_capacity::dealloc(self.ptr, cap),
-            Err(_) => {
-                // read our first few bytes to get our capacity
-                let mut usize_buf = [0u8; core::mem::size_of::<usize>()];
-                core::ptr::copy_nonoverlapping(
-                    self.ptr.as_ptr() as *const u8,
-                    usize_buf.as_mut_ptr(),
-                    core::mem::size_of::<usize>(),
-                );
-                let cap = usize::from_le_bytes(usize_buf);
+            Err(_) => drop_heap(self),
+        }
+    }
 
-                inner::heap_capacity::dealloc(self.ptr, cap)
-            }
+    /// Tries to reallocate the buffer, and sets the new capacity on success.
+    ///
+    /// Returns the new capacity as `Ok(…)` if the string was reallocated.
+    /// Or the old capacity as `Err(…)` if the string could not be reallocated.
+    fn realloc(&mut self, new_capacity: usize) -> Result<usize, ()> {
+        // can't reallocate a BoxString to a size less than the current length
+        if new_capacity < self.len {
+            return Err(());
         }
+
+        let cur_cap = self.cap.as_usize();
+        let new_cap = Capacity::new(new_capacity);
+
+        let (new_cap, new_ptr) = match (cur_cap, new_cap) {
+            // current capacity is the same as new, no realloc needed!
+            (Ok(cur), Ok(_)) if cur == new_capacity => {
+                return Ok(new_capacity);
+            }
+            // both current and new capacity can be stored inline
+            (Ok(cur), Ok(new_cap)) => {
+                let cur_layout = inner::inline_capacity::layout(cur);
+                let new_size = inner::inline_capacity::layout(new_capacity).size();
+
+                // attempt to reallocate, returning an error if we failed
+                match NonNull::new(unsafe {
+                    alloc::realloc(self.ptr.as_ptr(), cur_layout, new_size)
+                }) {
+                    Some(ptr) => (new_cap, ptr),
+                    None => return Err(()),
+                }
+            }
+            // capacity is currently on the heap, and needs to stay on the heap
+            (Err(_), Err(new_cap)) => {
+                let cur_layout = inner::heap_capacity::layout(self.capacity());
+                let new_size = inner::heap_capacity::layout(new_capacity).size();
+
+                // attempt to reallocate, returning an error if we failed
+                let ptr = match NonNull::new(unsafe {
+                    alloc::realloc(self.ptr.as_ptr(), cur_layout, new_size)
+                }) {
+                    Some(ptr) => ptr,
+                    None => return Err(()),
+                };
+
+                // our allocation succeeded! we need to write the new cap to the heap
+                unsafe {
+                    core::ptr::copy_nonoverlapping(
+                        new_capacity.to_le_bytes().as_ptr(),
+                        ptr.as_ptr(),
+                        core::mem::size_of::<usize>(),
+                    )
+                };
+
+                (new_cap, ptr)
+            }
+            // capacity is currently inline or on the heap, but needs to move, can't realloc!
+            (Ok(_), Err(_)) | (Err(_), Ok(_)) => {
+                return Err(());
+            }
+        };
+
+        // set our new pointer and new capacity
+        self.ptr = new_ptr;
+        self.cap = new_cap;
+
+        Ok(new_capacity)
     }
 }
 
@@ -646,23 +702,33 @@ mod tests {
         // assert the string is still correct
         assert_eq!(&format!("{}!", string), box_string.as_str());
 
-        // on 32-bit archs the capacity will be stored on the heap
-        #[cfg(target_pointer_width = "32")]
-        assert!(box_string.cap.as_usize().is_err());
-        // on 64-bit archs it's still inlined
-        #[cfg(not(target_pointer_width = "32"))]
-        assert!(box_string.cap.as_usize().is_ok());
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // on 64-bit archs it's still inlined
+                assert!(box_string.cap.as_usize().is_ok());
+            } else if #[cfg(target_pointer_width = "32")] {
+                // on 32-bit archs the capacity will be stored on the heap
+                assert!(box_string.cap.as_usize().is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
 
         // push a string
         box_string.push_str("hello!");
 
-        // on 32-bit archs the capacity will still be stored on the heap, since the capacity hasn't
-        // changed
-        #[cfg(target_pointer_width = "32")]
-        assert!(box_string.cap.as_usize().is_err());
-        // on 64-bit archs it's still inlined
-        #[cfg(not(target_pointer_width = "32"))]
-        assert!(box_string.cap.as_usize().is_ok());
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // on 64-bit archs it's still inlined
+                assert!(box_string.cap.as_usize().is_ok());
+            } else if #[cfg(target_pointer_width = "32")] {
+                // on 32-bit archs the capacity will still be stored on the heap, since the capacity
+                // hasn't changed
+                assert!(box_string.cap.as_usize().is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
 
         // assert the string is still correct
         assert_eq!(&format!("{}!hello!", string), box_string.as_str());
@@ -679,12 +745,17 @@ mod tests {
 
         let mut box_string = BoxString::new(&string);
 
-        // on 32-bit archs the capacity will be stored on the heap
-        #[cfg(target_pointer_width = "32")]
-        assert!(box_string.cap.as_usize().is_err());
-        // on 64-bit archs it's still inlined
-        #[cfg(not(target_pointer_width = "32"))]
-        assert_eq!(box_string.cap.as_usize(), Ok(SIXTEEN_MB - 1));
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // on 64-bit archs it's still inlined
+                assert_eq!(box_string.cap.as_usize(), Ok(SIXTEEN_MB - 1));
+            } else if #[cfg(target_pointer_width = "32")] {
+                // on 32-bit archs the capacity will be stored on the heap
+                assert!(box_string.cap.as_usize().is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
 
         // assert the strings are equal
         assert_eq!(&string, box_string.as_str());
@@ -694,28 +765,108 @@ mod tests {
         // assert the string is still correct
         assert_eq!(&format!("{}!", string), box_string.as_str());
 
-        // on 32-bit archs the capacity will be stored on the heap
-        #[cfg(target_pointer_width = "32")]
-        assert!(box_string.cap.as_usize().is_err());
-        // on 64-bit archs it's still inlined
-        #[cfg(not(target_pointer_width = "32"))]
-        assert!(box_string.cap.as_usize().is_ok());
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // on 64-bit archs it's still inlined
+                assert!(box_string.cap.as_usize().is_ok());
+            } else if #[cfg(target_pointer_width = "32")] {
+                // on 32-bit archs the capacity will be stored on the heap
+                assert!(box_string.cap.as_usize().is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
 
         // push a string
         box_string.push_str("hello!");
 
-        // on 32-bit archs the capacity will still be stored on the heap, since the capacity hasn't
-        // changed
-        #[cfg(target_pointer_width = "32")]
-        assert!(box_string.cap.as_usize().is_err());
-        // on 64-bit archs it's still inlined
-        #[cfg(not(target_pointer_width = "32"))]
-        assert!(box_string.cap.as_usize().is_ok());
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // on 64-bit archs it's still inlined
+                assert!(box_string.cap.as_usize().is_ok());
+            } else if #[cfg(target_pointer_width = "32")] {
+                // on 32-bit archs the capacity will still be stored on the heap, since the capacity
+                // hasn't changed
+                assert!(box_string.cap.as_usize().is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
 
         // assert the string is still correct
         assert_eq!(&format!("{}!hello!", string), box_string.as_str());
     }
 
+    #[test]
+    fn test_realloc_inline_cap_to_inline_cap() {
+        let mut box_string = BoxString::from("hello");
+        // relloc to value < capacity::MAX_VALUE
+        let result = box_string.realloc(128);
+
+        assert_eq!(result.unwrap(), 128);
+        assert_eq!(box_string.as_str(), "hello");
+    }
+
+    #[test]
+    fn test_realloc_inline_cap_to_heap_cap() {
+        let mut box_string = BoxString::from("hello");
+        // relloc to a value > capacity::MAX_VALUE
+        let result = box_string.realloc(SIXTEEN_MB + 128);
+
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // realloc should succeed since on 64-bit platforms
+                assert_eq!(result.unwrap(), SIXTEEN_MB + 128);
+            } else if #[cfg(target_pointer_width = "32")] {
+                // realloc should fail since we need to go from inline capacity -> heap
+                assert!(result.is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
+
+        assert_eq!(box_string.as_str(), "hello");
+    }
+
+    #[test]
+    fn test_realloc_heap_cap_to_heap_cap() {
+        let mut box_string = BoxString::with_capacity(SIXTEEN_MB + 128);
+        box_string.push_str("hello");
+        assert_eq!(box_string.as_str(), "hello");
+        assert_eq!(box_string.capacity(), SIXTEEN_MB + 128);
+
+        // relloc to a value > capacity::MAX_VALUE
+        let result = box_string.realloc(SIXTEEN_MB + 256);
+
+        assert_eq!(result.unwrap(), SIXTEEN_MB + 256);
+        assert_eq!(box_string.as_str(), "hello");
+    }
+
+    #[test]
+    fn test_realloc_heap_cap_to_inline_cap() {
+        let mut box_string = BoxString::with_capacity(SIXTEEN_MB + 128);
+        box_string.push_str("hello");
+        assert_eq!(box_string.as_str(), "hello");
+        assert_eq!(box_string.capacity(), SIXTEEN_MB + 128);
+
+        // relloc to a value < capacity::MAX_VALUE
+        let result = box_string.realloc(128);
+
+        cfg_if::cfg_if! {
+            if #[cfg(target_pointer_width = "64")] {
+                // realloc should succeed since on 64-bit platforms
+                assert_eq!(result.unwrap(), 128);
+            } else if #[cfg(target_pointer_width = "32")] {
+                // realloc should fail since we need to go from inline capacity -> heap
+                assert!(result.is_err());
+            } else {
+                compile_error!("Unsupported target_pointer_width");
+            }
+        }
+
+        assert_eq!(box_string.as_str(), "hello");
+    }
+
     #[proptest]
     #[cfg_attr(miri, ignore)]
     fn proptest_strings_roundtrip(#[strategy(rand_unicode())] word: String) {
diff --git a/fuzz/Cargo.toml b/fuzz/Cargo.toml
index 3d64d3a1..b188d6e4 100644
--- a/fuzz/Cargo.toml
+++ b/fuzz/Cargo.toml
@@ -32,6 +32,12 @@ test = false
 doc = false
 required-features = ["afl"]
 
+[[bin]]
+name = "debug"
+path = "src/bin/debug.rs"
+test = false
+doc = false
+
 [[bin]]
 name = "honggfuzz"
 path = "src/bin/honggfuzz.rs"
diff --git a/fuzz/src/bin/debug.rs b/fuzz/src/bin/debug.rs
new file mode 100644
index 00000000..4364fd33
--- /dev/null
+++ b/fuzz/src/bin/debug.rs
@@ -0,0 +1,26 @@
+//! Binary that allows you to pass an input file, it creates a [`compact_str_fuzz::Scenario`] and
+//! then runs it.
+//!
+//! This is helpful when AFL finds failures and we need to reproduce them.
+
+use std::path::PathBuf;
+
+use arbitrary::{
+    Arbitrary,
+    Unstructured,
+};
+use compact_str_fuzz::Scenario;
+
+pub fn main() {
+    let path = std::env::args()
+        .nth(1)
+        .map(PathBuf::from)
+        .expect("no path provided!");
+    let data = std::fs::read(path).expect("failed to read input file");
+    let mut unstructured = Unstructured::new(&data);
+    let scenario = Scenario::arbitrary(&mut unstructured).expect("failed to create Scenario");
+
+    println!("Scenario: {:?}", scenario);
+
+    scenario.run();
+}


Test patch:
diff --git a/compact_str/src/tests.rs b/compact_str/src/tests.rs
index 3e1af2fc..2ccfa3a1 100644
--- a/compact_str/src/tests.rs
+++ b/compact_str/src/tests.rs
@@ -1024,3 +1024,35 @@ fn test_insert() {
         "\u{ffff}\u{ffff}\u{ffff}\u{ffff}\u{ffff}\u{ffff}\u{ffff}\u{ffff}",
     );
 }
+
+#[test]
+fn test_with_capacity_16711422() {
+    // Fuzzing with AFL on a 32-bit ARM arch found this bug!
+    //
+    // We have our own heap implemenation called BoxString, which optionally stores the capacity
+    // on the heap, which is really only relevant for 32-bit architectures. The discriminant it used
+    // to determine if capacity was on the heap, was when the last `usize` number of bytes were all
+    // equal to our internal HEAP_MASK, which at the time was `255`. At the time this worked and was
+    // correct.
+    //
+    // When we released support to make the size of CompactString == Option<CompactString>, we
+    // changed the HEAP_MASK to `254`, which unintentionally made our discriminant for determining
+    // if our capacity was on the heap, all `254`s, yet our "max inline capacity value" was still
+    // based on the discriminant being all `255`s.
+    //
+    // When creating a BoxString with capacity 16711422, we'd correctly decide we could store the
+    // capacity inline, but this would create a capacity with an underlying value of
+    // [254, 254, 254, HEAP_MASK]. Once the HEAP_MASK changed to 254, this capacity was now the same
+    // as the discriminant to determine if the capacity was on the heap, so we'd incorrectly
+    // identify the capacity as being on the heap, when it was really inline.
+
+    assert_eq!(16711422_u32.to_le_bytes(), [254, 254, 254, 0]);
+
+    let compact = CompactString::with_capacity(16711422);
+    let std_str = String::with_capacity(16711422);
+
+    assert!(compact.is_heap_allocated());
+    assert_eq!(compact.capacity(), std_str.capacity());
+    assert_eq!(compact, "");
+    assert_eq!(compact, std_str);
+}