Implementare una funzione per verificare se un array stringa/byte segue il formato utf-8

Question

Sto cercando di risolvere questa domanda di intervista.

Dopo aver dato una chiara definizione del formato UTF-8. es: 1-byte: 0b0xxxxxxx 2 byte: .... Chiede di scrivere una funzione per verificare se l'input è valido UTF-8. L'input sarà array stringa/byte, l'uscita dovrebbe essere sì/no.

Ho due possibili approcci.

Innanzitutto, se l'input è una stringa, poiché UTF-8 è al massimo 4 byte, dopo aver rimosso i primi due caratteri "0b", è possibile utilizzare Integer.parseInt (s) per verificare se il resto del la stringa è compresa tra 0 e 10FFFF. Inoltre, è meglio controllare se la lunghezza della stringa è un multiplo di 8 e se la stringa di input contiene prima tutti gli 0 e gli 1. Quindi dovrò passare attraverso la stringa due volte e la complessità sarà O (n).

In secondo luogo, se l'input è un array di byte (possiamo anche utilizzare questo metodo se l'input è una stringa), controlliamo se ciascun elemento da 1 byte è nell'intervallo corretto. Se l'input è una stringa, prima controlla che la lunghezza della stringa sia un multiplo di 8, quindi verifica che ogni sottostringa di 8 caratteri sia compresa nell'intervallo.

So che esistono soluzioni di coppia su come controllare una stringa utilizzando le librerie Java, ma la mia domanda è come dovrei implementare la funzione in base alla domanda.

Grazie mille.

Answer 1

Bene, sono grato per i commenti e la risposta. Prima di tutto, devo convenire che questa è "un'altra stupida domanda di intervista". È vero che in Java String è già codificato, quindi sarà sempre compatibile con UTF-8. Un modo per controllare è dato una stringa:

public static boolean isUTF8(String s){ 
    try{ 
     byte[]bytes = s.getBytes("UTF-8"); 
    }catch(UnsupportedEncodingException e){ 
     e.printStackTrace(); 
     System.exit(-1); 
    } 
    return true; 
} 

Tuttavia, dal momento che tutte le stringhe stampabili sono in forma unicode, quindi non ho avuto la possibilità di ottenere un errore.

Secondo, se viene fornito un array di byte, sarà sempre compreso nell'intervallo -2^7 (0b10000000) in 2^7 (0b1111111), quindi sarà sempre in un intervallo UTF-8 valido.

La mia comprensione iniziale alla domanda era che, data una stringa, diciamo "0b11111111", controlla se è un UTF-8 valido, immagino di aver sbagliato.

Inoltre, Java fornisce il costruttore per convertire l'array di byte in stringa e, se si è interessati al metodo di decodifica, controllare.

Un'altra cosa, la risposta sopra sarebbe corretta data un'altra lingua. L'unico miglioramento potrebbe essere:

Nel novembre 2003, UTF-8 è stato limitato da RFC 3629 alla fine a U + 10FFFF, in modo da corrispondere ai vincoli della codifica di caratteri UTF-16. Ciò ha rimosso tutte le sequenze a 5 e 6 byte e circa la metà delle sequenze a 4 byte.

Quindi 4 byte sarebbero sufficienti.

Sono assolutamente a questo, quindi correggimi se sbaglio. Molte grazie.

Answer 2

Diamo prima un'occhiata a visual representation of the UTF-8 design.

---

Ora cerchiamo di riprendere quello che dobbiamo fare.

• Loop su tutti i caratteri della stringa (ogni carattere è un byte).
• Sarà necessario applicare una maschera a ciascun byte in base al punto di codice poiché i caratteri x rappresentano il punto di codice effettivo. Utilizzeremo l'operatore AND binario (&) che copia un bit nel risultato se esiste in entrambi gli operandi.
• L'obiettivo dell'applicazione di una maschera è di rimuovere i bit finali in modo da confrontare il byte effettivo come primo punto di codice. Effettueremo l'operazione bit a bit usando 0b1xxxxxxx dove 1 apparirà "Bytes in sequenza" e altri bit saranno 0.
• Possiamo quindi confrontare con il primo byte per verificare se è valido e anche determinare quale è il byte effettivo.
• Se il carattere inserito in nessuno dei casi, significa che il byte non è valido e restituiamo "No".
• Se siamo in grado di uscire dal ciclo, significa che ogni carattere è valido, quindi la stringa è valida.
• Assicurarsi che il confronto restituito true corrisponda alla lunghezza prevista.

---

Il metodo sarebbe simile a questa:

public static final boolean isUTF8(final byte[] pText) { 

    int expectedLength = 0; 

    for (int i = 0; i < pText.length; i++) { 
     if ((pText[i] & 0b10000000) == 0b00000000) { 
      expectedLength = 1; 
     } else if ((pText[i] & 0b11100000) == 0b11000000) { 
      expectedLength = 2; 
     } else if ((pText[i] & 0b11110000) == 0b11100000) { 
      expectedLength = 3; 
     } else if ((pText[i] & 0b11111000) == 0b11110000) { 
      expectedLength = 4; 
     } else if ((pText[i] & 0b11111100) == 0b11111000) { 
      expectedLength = 5; 
     } else if ((pText[i] & 0b11111110) == 0b11111100) { 
      expectedLength = 6; 
     } else { 
      return false; 
     } 

     while (--expectedLength > 0) { 
      if (++i >= pText.length) { 
       return false; 
      } 
      if ((pText[i] & 0b11000000) != 0b10000000) { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

---

Edit: Il metodo attuale non è quella originale (quasi, ma non) ed è stato rubato da here. Quello originale non funzionava correttamente secondo il commento di @EJP.

Answer 3

il CharsetDecoder potrebbe essere quello che stai cercando:

@Test 
public void testUTF8() throws CharacterCodingException { 
    // the desired charset 
    final Charset UTF8 = Charset.forName("UTF-8"); 
    // prepare decoder 
    final CharsetDecoder decoder = UTF8.newDecoder(); 
    decoder.onMalformedInput(CodingErrorAction.REPORT); 
    decoder.onUnmappableCharacter(CodingErrorAction.REPORT); 

    byte[] bytes = new byte[48]; 
    new Random().nextBytes(bytes); 
    ByteBuffer buffer = ByteBuffer.wrap(bytes); 
    try { 
     decoder.decode(buffer); 
     fail("Should not be UTF-8"); 
    } catch (final CharacterCodingException e) { 
     // noop, the test should fail here 
    } 

    final String string = "hallo welt!"; 
    bytes = string.getBytes(UTF8); 
    buffer = ByteBuffer.wrap(bytes); 
    final String result = decoder.decode(buffer).toString(); 
    assertEquals(string, result); 
} 

così la funzione potrebbe essere simile che:

public static boolean checkEncoding(final byte[] bytes, final String encoding) { 
    final CharsetDecoder decoder = Charset.forName(encoding).newDecoder(); 
    decoder.onMalformedInput(CodingErrorAction.REPORT); 
    decoder.onUnmappableCharacter(CodingErrorAction.REPORT); 
    final ByteBuffer buffer = ByteBuffer.wrap(bytes); 

    try { 
     decoder.decode(buffer); 
     return true; 
    } catch (final CharacterCodingException e) { 
     return false; 
    } 
} 

Answer 4

public static boolean validUTF8(byte[] input) { 
    int i = 0; 
    // Check for BOM 
    if (input.length >= 3 && (input[0] & 0xFF) == 0xEF 
      && (input[1] & 0xFF) == 0xBB & (input[2] & 0xFF) == 0xBF) { 
     i = 3; 
    } 

    int end; 
    for (int j = input.length; i < j; ++i) { 
     int octet = input[i]; 
     if ((octet & 0x80) == 0) { 
      continue; // ASCII 
     } 

     // Check for UTF-8 leading byte 
     if ((octet & 0xE0) == 0xC0) { 
      end = i + 1; 
     } else if ((octet & 0xF0) == 0xE0) { 
      end = i + 2; 
     } else if ((octet & 0xF8) == 0xF0) { 
      end = i + 3; 
     } else { 
      // Java only supports BMP so 3 is max 
      return false; 
     } 

     while (i < end) { 
      i++; 
      octet = input[i]; 
      if ((octet & 0xC0) != 0x80) { 
       // Not a valid trailing byte 
       return false; 
      } 
     } 
    } 
    return true; 
}