5

For example, let's say I want to delete from the array all continuous segments of 0's longer than 3 bytes

byte a[] = {1,2,3,0,1,2,3,0,0,0,0,4};
byte r[] = magic(a);
System.out.println(r);

result

{1,2,3,0,1,2,3,4}

I want to do something like a regular expression in Java, but on a byte array instead of a String.

Is there something that can help me built-in (or is there a good third party tool), or do I need to work from scratch?

Strings are UTF-16, so converting back and forth isn't a good idea? At least it's a lot of wasted overhead ... right?

4
  • How critical is performance and memory usage for your use case? In general, RAM is cheap and CPUs are fast. Have you actually found a bottleneck or is it a case of worrying about efficiency? You can easily try it out by converting byte [] to String using an 8-bit encoding, do your regexing and check the performance. After all, we don't worry about how inefficient Java strings with their 16-bit chars are for normal usage in ANSI environments, right? Sep 7, 2009 at 0:00
  • 1
    It's for a high performance application, I'm more worried about cycles than ram use.
    – Mike
    Sep 7, 2009 at 0:02
  • 1
    It's still worth benchmarking; a Hotspot VM will convert code in hotspots to machine code, which will handle 16-bit data at the same speed as 8-bit data since it all fits into a 32-bit machine word. Even if you find its too slow, you won't have spent much time finding it out. Sep 7, 2009 at 0:08
  • true, i think i'm gonna try anyway, thanks
    – Mike
    Sep 7, 2009 at 0:12

8 Answers 8

26
byte[] a = {1,2,3,0,1,2,3,0,0,0,0,4};
String s0 = new String(a, "ISO-8859-1");
String s1 = s0.replaceAll("\\x00{4,}", "");
byte[] r = s1.getBytes("ISO-8859-1");

System.out.println(Arrays.toString(r)); // [1, 2, 3, 0, 1, 2, 3, 4]

I used ISO-8859-1 (latin1) because, unlike any other encoding,

  • every byte in the range 0x00..0xFF maps to a valid character, and

  • each of those characters has the same numeric value as its latin1 encoding.

That means the string is the same length as the original byte array, you can match any byte by its numeric value with the \xFF construct, and you can convert the resulting string back to a byte array without losing information.

I wouldn't try to display the data while it's in string form--although all the characters are valid, many of them are not printable. Also, avoid manipulating the data while it's in string form; you might accidentally do some escape-sequence substitutions or another encoding conversion without realizing it. In fact, I wouldn't recommend doing this kind of thing at all, but that isn't what you asked. :)

Also, be aware that this technique won't necessarily work in other programming languages or regex flavors. You would have to test each one individually.

0
8

Though I question whether reg-ex is the right tool for the job, if you do want to use one I'd suggest you just implement a CharSequence wrapper on a byte array. Something like this (I just wrote this directly in, not compiled... but you get the idea).

public class ByteChars 
implements CharSequence

...

ByteChars(byte[] arr) {
    this(arr,0,arr.length);
    }

ByteChars(byte[] arr, int str, int end) {
    //check str and end are within range here
    strOfs=str;
    endOfs=end;
    bytes=arr;
    }

public char charAt(int idx) { 
    //check idx is within range here
    return (char)(bytes[strOfs+idx]&0xFF); 
    }

public int length() { 
    return (endOfs-strOfs); 
    }

public CharSequence subSequence(int str, int end) { 
    //check str and end are within range here
    return new ByteChars(arr,(strOfs+str,strOfs+end); 
    }

public String toString() { 
    return new String(bytes,strOfs,(endOfs-strOfs),"ISO8859_1");
    }
1
  • I implemented this approach and it worked a treat! Obviously you have to be careful since you're not performing any charset decoding, but for things like doctype detection it's perfect.
    – sigpwned
    Mar 8, 2015 at 15:35
1

regex is not the tool for the job, you will instead need to implement that from scratch

0
1

I don't see how regex would be useful to do what you want. One thing you can do is use Run Length Encoding to encode that byte array, replace every ocurrence of "30" (read three 0's) with the empty string, and decode the final string. Wikipedia has a simple Java implementation of it.

1
  • 1
    I thought the 3 0s was just an example. Sep 6, 2009 at 23:57
1

Although there's a reasonable ByteString library floating around, nobody that I've seen has implemented a general regexp library on them.

I recommend solving your problem directly rather than implementing a regexp library :)

If you do convert to string and back, you probably won't find any existing encoding that gives you a round trip for your 0 bytes. If that's the case, you'd have to write your own byte array <-> string converters; not worth the trouble.

0

I'd suggest converting the byte array into a String, performing the regex, and then converting it back. Here's a working example:

public void testRegex() throws Exception {
    byte a[] = { 1, 2, 3, 0, 1, 2, 3, 0, 0, 0, 0, 4 };
    String s = btoa(a);
    String t = s.replaceAll("\u0000{4,}", "");
    byte b[] = atob(t);
    System.out.println(Arrays.toString(b));
}

private byte[] atob(String t) {
    char[] array = t.toCharArray();
    byte[] b = new byte[array.length];
    for (int i = 0; i < array.length; i++) {
        b[i] = (byte) Character.toCodePoint('\u0000', array[i]);
    }
    return b;
}

private String btoa(byte[] a) {
    StringBuilder sb = new StringBuilder();
    for (byte b : a) {
        sb.append(Character.toChars(b));
    }
    return sb.toString();
}

For more complicated transformations, I'd suggest using a Lexer. Both JavaCC and ANTLR have support for parsing/transforming binary files.

0

The implementation utilizing a Regular Expression, proposed by other answers, is up to 8 times slower than a naive implementation using a loop that copies bytes from the input array to an output array.

The implementation copies an input array byte by byte. If a zero sequence was detected, the output array index is reduced (rewound). After processing the input array, the output array is even copied once more to trim its length to the actual number of bytes since the intermediate output array is initialized with the length of the input array.

/**
 * Remove four or more zero byte sequences from the input array.
 *  
 * @param inBytes the input array 
 * @return a new array with four or more zero bytes removed form the input array
 */
private static byte[] removeDuplicates(byte[] inBytes) {
    int size = inBytes.length;
    // Use an array with the same size in the first place
    byte[] newBytes = new byte[size];
    byte value;
    int newIdx = 0;
    int zeroCounter = 0;

    for (int i = 0; i < size; i++) {
        value = inBytes[i];

        if (value == 0) {
            zeroCounter++;
        } else {
            if (zeroCounter >= 4) {
                // Rewind output buffer index
                newIdx -= zeroCounter;
            }

            zeroCounter = 0;
        }

        newBytes[newIdx] = value;
        newIdx++;
    }

    if (zeroCounter >= 4) {
        // Rewind output buffer index for four zero bytes at the end too
        newIdx -= zeroCounter;
    }

    // Copy data into an array that has the correct length
    byte[] finalOut = new byte[newIdx];
    System.arraycopy(newBytes, 0, finalOut, 0, newIdx);

    return finalOut;
}

A second approach that would prevent unnecessary copies by rewinding to the first zero byte (of three or less) and copying those elements was interestingly a bit slower than the first approach.

All three implementations were tested on a Pentium N3700 processor with 1,000 iterations over a 8 x 32KB input array with several amounts and lengths of zero sequences. The worst performance improvement compared to the Regular Expression approach was 1.5x faster.

The full test rig can be found here: https://pastebin.com/83q9EzDc

-1

Java Regex operates on CharSequences - you could CharBuffer to wrap your existing byte array (you might need to cast it to char[] ?) and interpret it as such, and then perform regex on that?

1
  • Bad grammar, no code, either Unicode replacement question marks or counter questions. Hard to understand for people asking such X/Y questions. Downvoted until improved. Jul 30, 2017 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.