DEV Community: João Paulo Martins Silva

Revisiting Two's complement: A demonstration using Java

João Paulo Martins Silva — Tue, 03 Dec 2024 22:08:06 +0000

public class Main {
    public static void main(String[] args) {
        int number = 1;
        int invertedNumber = ~number; // Invert bits using the ~ operator
        int invertedNumberPlusOne = invertedNumber + 1;
        System.out.println("Number = " + number + " Binary value: " + Integer.toBinaryString(number));
        System.out.println("Inverted number = " + invertedNumber + " Binary value: " + Integer.toBinaryString(invertedNumber));
        System.out.println("Negative number = " + invertedNumberPlusOne + " Binary value: " + Integer.toBinaryString(invertedNumberPlusOne));
    }
}

Output:

Number = 1 Binary value: 1
Inverted number = -2 Binary value: 11111111111111111111111111111110
Negative number = -1 Binary value: 11111111111111111111111111111111

At first glance, this code might seem nonsensical, but it demonstrates how computers represent negative numbers in binary using two's complement. In this example, the number 1 is converted to -1 by inverting its bits and adding 1.

How Does Two's Complement Work?

Two's complement is a mathematical trick for efficiently representing negative numbers in binary. The leading bit defines if a number is positive(0) or negative(1). The process involves:

Inverting the bits of the binary representation of the number.
Adding 1 to the inverted result.

But why does this work? It’s tied to how binary subtraction operates. When transforming a number into its negative counterpart, you’re essentially subtracting the number from 0. For example:

Similar to decimal subtraction, binary subtraction follows the borrowing rule (reference here).
In most systems, binary numbers are stored in fixed-width variables (e.g., 8 bits). Any extra bits from the computation are simply discarded, which means subtracting 01001011 from 100000000 (1 followed by 8 zeros) is functionally identical to subtracting it from 0.

Here’s what happens when you carry out this subtraction:

By splitting the computation into two steps:
1 + 11111111 = 100000000.

The result is the same as performing a direct subtraction.

In essence, subtracting a binary number ( A ) from an all-ones number is equivalent to inverting the bits of ( A ). The Java program leverages this trick to efficiently compute the negative of a number using two's complement.

Key Takeaway:

The Java program illustrates a clever use of two's complement for converting a binary number into its negative counterpart. If you don't remember how a negative number is stored in binary this link can help.

Source: Cornell University: Two's Complement Notes

Exploring the Impact of Java Integer Cache on Performance: A JMH Benchmark Study

João Paulo Martins Silva — Thu, 09 May 2024 00:53:32 +0000

In one of my posts, I made 2 + 2 equal to 5 using Java 21. In summary, the Integer class in Java has a cache for values from -128 to 127. I manipulated these values by swapping the number 4 with 5. This made me ponder the importance of this cache and its impact on a program. So, I decided to conduct a test using JMH, which is a micro benchmark API. In this test, I instantiated an array of Integers of various different sizes, both within and outside the range of cached values, and measured the execution time of each case in nanoseconds.

package com.benchmark.integer.cache;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;

public class BenchMark {

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached1() {
        return instanciateNumbers(1, true);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached100() {
        return instanciateNumbers(100, true);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached1000() {
        return instanciateNumbers(1000, true);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached10000() {
        return instanciateNumbers(10000, true);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached100000() {
        return instanciateNumbers(100000, true);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List cached1000000() {
        return instanciateNumbers(1000000, true);
    }

    ////////////////////////////////////////////////
    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache1() {
        return instanciateNumbers(1, false);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache100() {
        return instanciateNumbers(100, false);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache1000() {
        return instanciateNumbers(1000, false);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache10000() {
        return instanciateNumbers(10000, false);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache100000() {
        return instanciateNumbers(100000, false);
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.SECONDS)
    @BenchmarkMode(Mode.AverageTime)
    public List OutOfRangeCache1000000() {
        return instanciateNumbers(1000000, false);
    }

    public static List instantiateNumbers(int quantity, boolean minorThan128) {
        List<Integer> numeros = new ArrayList<>();
        if (minorThan128) {
            for (int i = 0; i < 128 && i < quantity; i++) {
                numeros.add(i);
            }
        } else {
            for (int i = 128; i < Integer.MAX_VALUE && numeros.size() < quantity; i++) {
                numeros.add(i);
            }
        }

        return numeros;
    }
}

After the JMH runner is executed it generated the following results:

As we can see, in the cases with 1 and 100 integers, the execution time is similar for both the cached and non-cached cases. But as it grows, the execution time for the non-cached cases doesn't stop increasing. In the cached tests, the execution time remains constant. After this test, my curiosity was satisfied; the integer cache has a significant impact on performance. Please feel free to comment or make any suggestions.

Bonus:

If you want to increase the integer cache you set VM parameter or System property like:

-Djava.lang.Integer.IntegerCache.high=256

Github:
https://github.com/joao9aulo/benchmark-integer-cache

Sources:

https://stackoverflow.com/questions/30277106/how-to-increase-the-cache-size-for-integer-object
https://www.baeldung.com/java-microbenchmark-harness

A Quine that is also an HTTP server.

João Paulo Martins Silva — Mon, 25 Mar 2024 22:33:22 +0000

I've always been fascinated by the concept of a Quine. I decided to implement my own version, only a bit different. To recap, a Quine is a program whose output is its own source code. For example, as in this project on GitHub implementing a Quine in various versions of Java:

An example of a Quine in Java:

public class Quine {
 public static void main(String[] args) {
  String textBlockQuotes = new String(new char[]{'"', '"', '"'});
  char newLine = 10;
  String source = """
public class Quine {
 public static void main(String[] args) {
  String textBlockQuotes = new String(new char[]{'"', '"', '"'});
  char newLine = 10;
  String source = %s;
  System.out.print(source.formatted(textBlockQuotes + newLine + source + textBlockQuotes));
 }
}
""";
  System.out.print(source.formatted(textBlockQuotes + newLine + source + textBlockQuotes));
 }
}`

My project aims to create an HTTP server encapsulated in a JAR file that, upon receiving a request, generates a new JAR containing its own source code. This new JAR, when executed, starts a replica of the original server, thus creating a self-replicating server.

Initially, the code generates a Jar containing the program's own compiled source code. To do this, a String containing it is first created.

String code = """
        package com.server.quine;

        import javax.tools.JavaCompiler;
        import javax.tools.ToolProvider;
        import java.io.*;
        import java.net.ServerSocket;
        import java.net.Socket;
        import java.nio.charset.StandardCharsets;
        import java.nio.file.Files;
        import java.util.jar.Attributes;
        import java.util.jar.JarEntry;
        import java.util.jar.JarOutputStream;
        import java.util.jar.Manifest;

        public class QuineServer {

            public static void main(String[] args) throws IOException {
                // Cria um arquivo JAR
                ByteArrayOutputStream jarOutputStream = createJarFile();

                // Cria o socket do servidor
                ServerSocket serverSocket = new ServerSocket(8080);

                while (true) {
                    // Espera por uma conexão
                    Socket socket = serverSocket.accept();
                    System.out.println("Aceitou a conexão");

                    // Escreve a resposta
                    try (OutputStream output = socket.getOutputStream()) {
                        // Escreve cabeçalhos HTTP para download do arquivo
                        PrintWriter writer = new PrintWriter(output, true);
                        writer.println("HTTP/1.1 200 OK");
                        writer.println("Server: Java HTTP Server: 1.0");
                        writer.println("Date: " + new java.util.Date());
                        writer.println("Content-type: application/java-archive");
                        writer.println("Content-length: " + jarOutputStream.toByteArray().length);
                        writer.println("Content-Disposition: attachment; filename=QuineServer.jar");
                        writer.println(); // Linha em branco entre os cabeçalhos e o conteúdo
                        writer.flush();

                        output.write(jarOutputStream.toByteArray());
                        output.flush();
                    }

                    // Fecha a conexão
                    socket.close();
                }
            }

            private static ByteArrayOutputStream createJarFile() throws IOException {
                String source = buildSourceCode();
                JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
                File tempDir = Files.createTempDirectory("test").toFile();
                File sourceFile = new File(tempDir, "test/QuineServer.java");
                sourceFile.getParentFile().mkdirs();
                Files.write(sourceFile.toPath(), source.getBytes(StandardCharsets.UTF_8));

                compiler.run(null, null, null, "-d", tempDir.getAbsolutePath(), sourceFile.getPath());

                File classFile = new File(tempDir, "com/server/quine/QuineServer.class");
                byte[] classBytes = Files.readAllBytes(classFile.toPath());

                // Cria o Manifesto
                Manifest manifest = new Manifest();
                manifest.getMainAttributes().put(Attributes.Name.MANIFEST_VERSION, "1.0");
                manifest.getMainAttributes().put(Attributes.Name.MAIN_CLASS, "com.server.quine.QuineServer");

                ByteArrayOutputStream jarOutputStream = new ByteArrayOutputStream();
                JarOutputStream jarOut = new JarOutputStream(jarOutputStream, manifest);

                // Adiciona a classe ao JAR
                JarEntry classEntry = new JarEntry("com/server/quine/QuineServer.class");
                jarOut.putNextEntry(classEntry);
                jarOut.write(classBytes);
                jarOut.closeEntry();
                // Fecha o JarOutputStream
                jarOut.close();

                return jarOutputStream;
            }

            private static String buildSourceCode() {
                String textBlockQuotes = new String(new char[]{'"', '"', '"'});
                char newLine = 10;
                String code = %s;
                String formatedCode = code.formatted( textBlockQuotes + newLine + code + textBlockQuotes);
                return formatedCode;
            }
        }
                                        """;

This same code contains a parameter in which its own content is passed. Thus, a source code containing itself recursively will always be generated.

The formatted method of the String class takes care of this.

String formatedCode = code.formatted(textBlockQuotes + newLine + code + textBlockQuotes);

Now that the String containing the source code has been created, it will be used to generate a file in a temporary folder. This file is the QuineServer.java class, that is, the very class that generated it.

File sourceFile = new File(tempDir, "test/QuineServer.java");
sourceFile.getParentFile().mkdirs();
Files.write(sourceFile.toPath(), source.getBytes(StandardCharsets.UTF_8));

To compile this source code dynamically within the program, the JavaCompiler class is used.

In this section, the result of the compilation, the .class file, is generated inside the temporary folder.

compiler.run(null, null, null, "-d", tempDir.getAbsolutePath(), sourceFile.getPath());

The content of the new file is stored in a variable.

File classFile = new File(tempDir, "com/server/quine/QuineServer.class");
byte[] classBytes = Files.readAllBytes(classFile.toPath());

With the code compiled, it's time to create the Jar. The following code generates a Manifest file and packages the compiled code.

// Cria o Manifesto
Manifest manifest = new Manifest();
manifest.getMainAttributes().put(Attributes.Name.MANIFEST_VERSION, "1.0");
manifest.getMainAttributes().put(Attributes.Name.MAIN_CLASS, "com.server.quine.QuineServer");

ByteArrayOutputStream jarOutputStream = new ByteArrayOutputStream();
JarOutputStream jarOut = new JarOutputStream(jarOutputStream, manifest);

// Adiciona a classe ao JAR
JarEntry classEntry = new JarEntry("com/server/quine/QuineServer.class");
jarOut.putNextEntry(classEntry);
jarOut.write(classBytes);
jarOut.closeEntry();
// Fecha o JarOutputStream
jarOut.close();

The code starts a server on port 8080. This server waits for incoming connections. When a connection is established, it responds by sending a JAR file, which was dynamically created by the program itself.

while (true) {
    // Espera por uma conexão
    Socket socket = serverSocket.accept();
    System.out.println("Aceitou a conexão");

    // Escreve a resposta
    try (OutputStream output = socket.getOutputStream()) {
        // Escreve cabeçalhos HTTP para download do arquivo
        PrintWriter writer = new PrintWriter(output, true);
        writer.println("HTTP/1.1 200 OK");
        writer.println("Server: Java HTTP Server: 1.0");
        writer.println("Date: " + new java.util.Date());
        writer.println("Content-type: application/java-archive");
        writer.println("Content-length: " + jarOutputStream.toByteArray().length);
        writer.println("Content-Disposition: attachment; filename=QuineServer.jar");
        writer.println(); // Linha em branco entre os cabeçalhos e o conteúdo
        writer.flush();

        output.write(jarOutputStream.toByteArray());
        output.flush();
    }

    // Fecha a conexão
    socket.close();
}

To test the self-replicating server, I created a script that runs the original JAR server, downloads the generated JAR, and repeats the process with the new JAR. This continuous loop results in the creation of multiple servers and JAR files.

#!/usr/bin/bash

# URL do arquivo JAR
JAR_URL="localhost:8080"
JAR_NAME="QuineServer.jar"

# Executa o arquivo JAR em segundo plano e armazena o PID
java -jar "$JAR_NAME" & JAR_PID=$!
sleep 1

while true; do
    # Gera um nome de arquivo baseado na data e hora atual ou extrai da URL
    JAR_NAME="arquivo_$(date +%Y%m%d%H%M%S).jar"
    # Ou use: JAR_NAME=$(basename "$JAR_URL")

    # Baixa o arquivo JAR
    echo "Iniciando o download de $JAR_URL..."
    wget -O "$JAR_NAME" "$JAR_URL"

    if [ $? -eq 0 ]; then
        echo "Download concluído com sucesso. Executando $JAR_NAME em segundo plano..."

        # Interrompe o processo do arquivo JAR
        echo "Interrompendo o processo do JAR (PID: $JAR_PID)."
        kill $JAR_PID
        # Executa o arquivo JAR em segundo plano e armazena o PID
        java -jar "$JAR_NAME" &
        JAR_PID=$!

        # Aguarda um determinado período antes de interromper o processo do JAR. Exemplo: 60 segundos
        sleep 1

        echo "Processo do JAR interrompido. Aguardando para a próxima execução..."
    else
        echo "Falha no download do arquivo. Tentando novamente..."
    fi

    # Aguarda novamente antes de repetir o processo, se necessário
    sleep 1
done

If you found this article interesting, and for some reason, you want to fill your HD with self-replicating jars, I've made the code available on my GitHub: .

Any suggestions or ideas, feel free to make a pull request or get in touch.

2 + 2 = 5 in Java 21

João Paulo Martins Silva — Mon, 26 Feb 2024 23:49:53 +0000

A few years ago, I found a video by podcaster Lex Friedman where he demonstrates that it's possible to make 2+2 equal five in Java using some tricks.


import java.lang.reflect.Field;   
    public class Main {
        public static void main(String[] args) throws Exception {
            Class cache = Integer.class.getDeclaredClasses()[0];
            Field c = cache.getDeclaredField("cache");
            c.setAccessible(true);
            Integer[] array = (Integer[]) c.get(cache);
            array[132] = array[133];

            System.out.printf("%d",2 + 2);
        }
    }

Out of curiosity, I decided to run the code available in the video links and encountered the following error:

Exception in thread "main" java.lang.reflect.InaccessibleObjectException: Unable to make field static final java.lang.Integer[] java.lang.Integer$IntegerCache.cache accessible: module java.base does not "opens java.lang" to unnamed module @8efb846
 at java.base/java.lang.reflect.AccessibleObject.throwInaccessibleObjectException(AccessibleObject.java:391)
 at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:367)
 at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:315)
 at java.base/java.lang.reflect.Field.checkCanSetAccessible(Field.java:183)
 at java.base/java.lang.reflect.Field.setAccessible(Field.java:177)
 at Old2Plus2.main(Old2Plus2.java:7)

I realized that, for the newer versions of Java, this hack was no longer possible. Therefore, in this article, I will demonstrate how to perform this trick for Java 21.

The error message says that the java.base module is not open. This means that it is not possible to use reflection from the Main class created for this example. If you are not very familiar with modules, I recommend refreshing your memory.

In other words, in Java 21, it's harder to perform this kind of hack with the language. Fortunately, there is a class that allows us to neglect the module system: the sun.misc.Unsafe. This class is used to perform low-level operations and is not recommended for the everyday use of ordinary programmers.

Thus, the new version of the code that makes 2+2 = 5 would look like this:

import java.lang.reflect.Field;

public class New2Plus2 {
    public static void main(String[] args) throws Exception {
        Class usf = Class.forName("sun.misc.Unsafe");//pega o objeto que representa a classe Unsafe
        Field unsafeField = usf.getDeclaredField("theUnsafe");//pega o campo theUnsafe da classe Unsafe
        unsafeField.setAccessible(true);//define o campo theUnsafe como público
        sun.misc.Unsafe unsafe = (sun.misc.Unsafe)unsafeField.get(null);//pega o valor do campo theUnsafe, como ele é static é passado o parâmetro null
        Class<?> clazz = Class.forName("java.lang.Integer$IntegerCache");// pega o objeto que representa a classe IntegerCache
        Field field = clazz.getDeclaredField("cache");//pega o campo cache da classe IntegerCache
        Integer[] cache = (Integer[])unsafe.getObject(unsafe.staticFieldBase(field), unsafe.staticFieldOffset(field));//utiliza a classe Unsafe para pegar o cache de Integer
        cache[132] = cache[133];// troca o valor 4 pelo 5
        System.out.printf("2+2 = %d",2 + 2);
    }
}

Running the code above, you will see that the result of the addition will be 5. Obviously, I do not recommend using this code in production if you want to maintain your sanity and your job.

References:

https://github.com/joao9aulo/2plus2equals5

https://javax0.wordpress.com/2017/05/03/hacking-the-integercache-in-java-9/

https://www.youtube.com/watch?v=amXXYgu0eFY

https://ideone.com/o1h0hR

https://www.oracle.com/br/corporate/features/understanding-java-9-modules.html

https://www.baeldung.com/java-unsafe

2 + 2 = 5 em Java 21

João Paulo Martins Silva — Thu, 22 Feb 2024 23:28:45 +0000

Há alguns anos, encontrei um vídeo do podcaster Lex Friedman em que ele demonstra que é possível fazer 2+2 ser cinco em Java usando alguns truques.


import java.lang.reflect.Field;   
    public class Main {
        public static void main(String[] args) throws Exception {
            Class cache = Integer.class.getDeclaredClasses()[0];
            Field c = cache.getDeclaredField("cache");
            c.setAccessible(true);
            Integer[] array = (Integer[]) c.get(cache);
            array[132] = array[133];

            System.out.printf("%d",2 + 2);
        }
    }

Por curiosidade, resolvi rodar o código disponibilizado nos links do vídeo e me deparei com o seguinte erro:

Exception in thread "main" java.lang.reflect.InaccessibleObjectException: Unable to make field static final java.lang.Integer[] java.lang.Integer$IntegerCache.cache accessible: module java.base does not "opens java.lang" to unnamed module @8efb846
 at java.base/java.lang.reflect.AccessibleObject.throwInaccessibleObjectException(AccessibleObject.java:391)
 at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:367)
 at java.base/java.lang.reflect.AccessibleObject.checkCanSetAccessible(AccessibleObject.java:315)
 at java.base/java.lang.reflect.Field.checkCanSetAccessible(Field.java:183)
 at java.base/java.lang.reflect.Field.setAccessible(Field.java:177)
 at Old2Plus2.main(Old2Plus2.java:7)

Percebi que, para as novas versões do Java, esse hack não era mais possível. Portanto, neste artigo, irei demonstrar como realizar esse truque para o Java 21

A mensagem de erro diz que o módulo java.base não está aberto. Isso significa que não é possível usar reflexão a partir da classe Main criada para esse exemplo. Caso não tenha muita familiaridade com módulos, recomendo dar uma relembrada.

Ou seja, no Java 21, é mais difícil fazer esse tipo de hack com a linguagem. Felizmente, existe uma classe que nos permite negligenciar o sistema de módulos: a sun.misc.Unsafe. Essa classe é utilizada para executar operações de baixo nível e não é recomendada para o dia a dia de programadores comuns.

Sendo assim, a nova versão do código que faz 2+2 = 5 ficaria dessa forma:

import java.lang.reflect.Field;

public class New2Plus2 {
    public static void main(String[] args) throws Exception {
        Class usf = Class.forName("sun.misc.Unsafe");//pega o objeto que representa a classe Unsafe
        Field unsafeField = usf.getDeclaredField("theUnsafe");//pega o campo theUnsafe da classe Unsafe
        unsafeField.setAccessible(true);//define o campo theUnsafe como público
        sun.misc.Unsafe unsafe = (sun.misc.Unsafe)unsafeField.get(null);//pega o valor do campo theUnsafe, como ele é static é passado o parâmetro null
        Class<?> clazz = Class.forName("java.lang.Integer$IntegerCache");// pega o objeto que representa a classe IntegerCache
        Field field = clazz.getDeclaredField("cache");//pega o campo cache da classe IntegerCache
        Integer[] cache = (Integer[])unsafe.getObject(unsafe.staticFieldBase(field), unsafe.staticFieldOffset(field));//utiliza a classe Unsafe para pegar o cache de Integer
        cache[132] = cache[133];// troca o valor 4 pelo 5
        System.out.printf("2+2 = %d",2 + 2);
    }
}