/*
    * Copyright 2012 The Netty Project
    *
    * The Netty Project licenses this file to you under the Apache License,
    * version 2.0 (the "License"); you may not use this file except in compliance
    * with the License. You may obtain a copy of the License at:
    *
    *   http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
   * License for the specific language governing permissions and limitations
   * under the License.
   */
  package org.jboss.netty.handler.codec.http;
  
  import org.jboss.netty.buffer.ChannelBuffer;
  import org.jboss.netty.buffer.ChannelBuffers;
  import org.jboss.netty.channel.Channel;
  import org.jboss.netty.channel.ChannelHandlerContext;
  import org.jboss.netty.channel.ChannelPipeline;
  import org.jboss.netty.handler.codec.frame.TooLongFrameException;
  import org.jboss.netty.handler.codec.replay.ReplayingDecoder;
  
  import java.util.List;
  
  /**
   * Decodes {@link ChannelBuffer}s into {@link HttpMessage}s and
   * {@link HttpChunk}s.
   *
   * <h3>Parameters that prevents excessive memory consumption</h3>
   * <table border="1">
   * <tr>
   * <th>Name</th><th>Meaning</th>
   * </tr>
   * <tr>
   * <td>{@code maxInitialLineLength}</td>
   * <td>The maximum length of the initial line
   *     (e.g. {@code "GET / HTTP/1.0"} or {@code "HTTP/1.0 200 OK"})
   *     If the length of the initial line exceeds this value, a
   *     {@link TooLongFrameException} will be raised.</td>
   * </tr>
   * <tr>
   * <td>{@code maxHeaderSize}</td>
   * <td>The maximum length of all headers.  If the sum of the length of each
   *     header exceeds this value, a {@link TooLongFrameException} will be raised.</td>
   * </tr>
   * <tr>
   * <td>{@code maxChunkSize}</td>
   * <td>The maximum length of the content or each chunk.  If the content length
   *     (or the length of each chunk) exceeds this value, the content or chunk
   *     will be split into multiple {@link HttpChunk}s whose length is
   *     {@code maxChunkSize} at maximum.</td>
   * </tr>
   * </table>
   *
   * <h3>Chunked Content</h3>
   *
   * If the content of an HTTP message is greater than {@code maxChunkSize} or
   * the transfer encoding of the HTTP message is 'chunked', this decoder
   * generates one {@link HttpMessage} instance and its following
   * {@link HttpChunk}s per single HTTP message to avoid excessive memory
   * consumption. For example, the following HTTP message:
   * <pre>
   * GET / HTTP/1.1
   * Transfer-Encoding: chunked
   *
   * 1a
   * abcdefghijklmnopqrstuvwxyz
   * 10
   * 1234567890abcdef
   * 0
   * Content-MD5: ...
   * <i>[blank line]</i>
   * </pre>
   * triggers {@link HttpRequestDecoder} to generate 4 objects:
   * <ol>
   * <li>An {@link HttpRequest} whose {@link HttpMessage#isChunked() chunked}
   *     property is {@code true},</li>
   * <li>The first {@link HttpChunk} whose content is {@code 'abcdefghijklmnopqrstuvwxyz'},</li>
   * <li>The second {@link HttpChunk} whose content is {@code '1234567890abcdef'}, and</li>
   * <li>An {@link HttpChunkTrailer} which marks the end of the content.</li>
   * </ol>
   *
   * If you prefer not to handle {@link HttpChunk}s by yourself for your
   * convenience, insert {@link HttpChunkAggregator} after this decoder in the
   * {@link ChannelPipeline}.  However, please note that your server might not
   * be as memory efficient as without the aggregator.
   *
   * <h3>Extensibility</h3>
   *
   * Please note that this decoder is designed to be extended to implement
   * a protocol derived from HTTP, such as
   * <a href="http://en.wikipedia.org/wiki/Real_Time_Streaming_Protocol">RTSP</a> and
   * <a href="http://en.wikipedia.org/wiki/Internet_Content_Adaptation_Protocol">ICAP</a>.
   * To implement the decoder of such a derived protocol, extend this class and
   * implement all abstract methods properly.
   * @apiviz.landmark
  */
 public abstract class HttpMessageDecoder extends ReplayingDecoder<HttpMessageDecoder.State> {
 
     private final int maxInitialLineLength;
     private final int maxHeaderSize;
     private final int maxChunkSize;
     private HttpMessage message;
     private ChannelBuffer content;
     private long chunkSize;
     private int headerSize;
     private int contentRead;
 
     /**
      * The internal state of {@link HttpMessageDecoder}.
      * <em>Internal use only</em>.
      * @apiviz.exclude
      */
     protected enum State {
         SKIP_CONTROL_CHARS,
         READ_INITIAL,
         READ_HEADER,
         READ_VARIABLE_LENGTH_CONTENT,
         READ_VARIABLE_LENGTH_CONTENT_AS_CHUNKS,
         READ_FIXED_LENGTH_CONTENT,
         READ_FIXED_LENGTH_CONTENT_AS_CHUNKS,
         READ_CHUNK_SIZE,
         READ_CHUNKED_CONTENT,
         READ_CHUNKED_CONTENT_AS_CHUNKS,
         READ_CHUNK_DELIMITER,
         READ_CHUNK_FOOTER
     }
 
     /**
      * Creates a new instance with the default
      * {@code maxInitialLineLength (4096}}, {@code maxHeaderSize (8192)}, and
      * {@code maxChunkSize (8192)}.
      */
     protected HttpMessageDecoder() {
         this(4096, 8192, 8192);
     }
 
     /**
      * Creates a new instance with the specified parameters.
      */
     protected HttpMessageDecoder(
             int maxInitialLineLength, int maxHeaderSize, int maxChunkSize) {
 
         super(State.SKIP_CONTROL_CHARS, true);
 
         if (maxInitialLineLength <= 0) {
             throw new IllegalArgumentException(
                     "maxInitialLineLength must be a positive integer: " +
                     maxInitialLineLength);
         }
         if (maxHeaderSize <= 0) {
             throw new IllegalArgumentException(
                     "maxHeaderSize must be a positive integer: " +
                     maxHeaderSize);
         }
         if (maxChunkSize < 0) {
             throw new IllegalArgumentException(
                     "maxChunkSize must be a positive integer: " +
                     maxChunkSize);
         }
         this.maxInitialLineLength = maxInitialLineLength;
         this.maxHeaderSize = maxHeaderSize;
         this.maxChunkSize = maxChunkSize;
     }
 
     @Override
     protected Object decode(
             ChannelHandlerContext ctx, Channel channel, ChannelBuffer buffer, State state) throws Exception {
         switch (state) {
         case SKIP_CONTROL_CHARS: {
             try {
                 skipControlCharacters(buffer);
                 checkpoint(State.READ_INITIAL);
             } finally {
                 checkpoint();
             }
         }
         case READ_INITIAL: {
             String[] initialLine = splitInitialLine(readLine(buffer, maxInitialLineLength));
             if (initialLine.length < 3) {
                 // Invalid initial line - ignore.
                 checkpoint(State.SKIP_CONTROL_CHARS);
                 return null;
             }
 
             message = createMessage(initialLine);
             checkpoint(State.READ_HEADER);
         }
         case READ_HEADER: {
             State nextState = readHeaders(buffer);
             checkpoint(nextState);
             if (nextState == State.READ_CHUNK_SIZE) {
                 // Chunked encoding
                 message.setChunked(true);
                 // Generate HttpMessage first.  HttpChunks will follow.
                 return message;
             } else if (nextState == State.SKIP_CONTROL_CHARS) {
                 // No content is expected.
                 // Remove the headers which are not supposed to be present not
                 // to confuse subsequent handlers.
                 message.removeHeader(HttpHeaders.Names.TRANSFER_ENCODING);
                 return message;
             } else {
                 long contentLength = HttpHeaders.getContentLength(message, -1);
                 if (contentLength == 0 || contentLength == -1 && isDecodingRequest()) {
                     content = ChannelBuffers.EMPTY_BUFFER;
                     return reset();
                 }
 
                 switch (nextState) {
                 case READ_FIXED_LENGTH_CONTENT:
                     if (contentLength > maxChunkSize || HttpHeaders.is100ContinueExpected(message)) {
                         // Generate HttpMessage first.  HttpChunks will follow.
                         checkpoint(State.READ_FIXED_LENGTH_CONTENT_AS_CHUNKS);
                         message.setChunked(true);
                         // chunkSize will be decreased as the READ_FIXED_LENGTH_CONTENT_AS_CHUNKS
                         // state reads data chunk by chunk.
                         chunkSize = HttpHeaders.getContentLength(message, -1);
                         return message;
                     }
                     break;
                 case READ_VARIABLE_LENGTH_CONTENT:
                     if (buffer.readableBytes() > maxChunkSize || HttpHeaders.is100ContinueExpected(message)) {
                         // Generate HttpMessage first.  HttpChunks will follow.
                         checkpoint(State.READ_VARIABLE_LENGTH_CONTENT_AS_CHUNKS);
                         message.setChunked(true);
                         return message;
                     }
                     break;
                 default:
                     throw new IllegalStateException("Unexpected state: " + nextState);
                 }
             }
             // We return null here, this forces decode to be called again where we will decode the content
             return null;
         }
         case READ_VARIABLE_LENGTH_CONTENT: {
             int toRead = actualReadableBytes();
             if (toRead > maxChunkSize) {
                 toRead = maxChunkSize;
             }
             if (!message.isChunked()) {
                 message.setChunked(true);
                 return new Object[] {message, new DefaultHttpChunk(buffer.readBytes(toRead))};
             } else {
                 return new DefaultHttpChunk(buffer.readBytes(toRead));
             }
         }
         case READ_VARIABLE_LENGTH_CONTENT_AS_CHUNKS: {
             // Keep reading data as a chunk until the end of connection is reached.
             int toRead = actualReadableBytes();
             if (toRead > maxChunkSize) {
                 toRead = maxChunkSize;
             }
             HttpChunk chunk = new DefaultHttpChunk(buffer.readBytes(toRead));
 
             if (!buffer.readable()) {
                 // Reached to the end of the connection.
                 reset();
                 if (!chunk.isLast()) {
                     // Append the last chunk.
                     return new Object[] { chunk, HttpChunk.LAST_CHUNK };
                 }
             }
             return chunk;
         }
         case READ_FIXED_LENGTH_CONTENT: {
             return readFixedLengthContent(buffer);
         }
         case READ_FIXED_LENGTH_CONTENT_AS_CHUNKS: {
             assert chunkSize <= Integer.MAX_VALUE;
             int chunkSize = (int) this.chunkSize;
             int readLimit = actualReadableBytes();
 
             // Check if the buffer is readable first as we use the readable byte count
             // to create the HttpChunk. This is needed as otherwise we may end up with
             // create a HttpChunk instance that contains an empty buffer and so is
             // handled like it is the last HttpChunk.
             //
             // See https://github.com/netty/netty/issues/433
             if (readLimit == 0) {
                 return null;
             }
 
             int toRead = chunkSize;
             if (toRead > maxChunkSize) {
                 toRead = maxChunkSize;
             }
             if (toRead > readLimit) {
                 toRead = readLimit;
             }
             HttpChunk chunk = new DefaultHttpChunk(buffer.readBytes(toRead));
             if (chunkSize > toRead) {
                 chunkSize -= toRead;
             } else {
                 chunkSize = 0;
             }
             this.chunkSize = chunkSize;
 
             if (chunkSize == 0) {
                 // Read all content.
                 reset();
                 if (!chunk.isLast()) {
                     // Append the last chunk.
                     return new Object[] { chunk, HttpChunk.LAST_CHUNK };
                 }
             }
             return chunk;
         }
         /**
          * everything else after this point takes care of reading chunked content. basically, read chunk size,
          * read chunk, read and ignore the CRLF and repeat until 0
          */
         case READ_CHUNK_SIZE: {
             String line = readLine(buffer, maxInitialLineLength);
             int chunkSize = getChunkSize(line);
             this.chunkSize = chunkSize;
             if (chunkSize == 0) {
                 checkpoint(State.READ_CHUNK_FOOTER);
                 return null;
             } else if (chunkSize > maxChunkSize) {
                 // A chunk is too large. Split them into multiple chunks again.
                 checkpoint(State.READ_CHUNKED_CONTENT_AS_CHUNKS);
             } else {
                 checkpoint(State.READ_CHUNKED_CONTENT);
             }
         }
         case READ_CHUNKED_CONTENT: {
             assert chunkSize <= Integer.MAX_VALUE;
             HttpChunk chunk = new DefaultHttpChunk(buffer.readBytes((int) chunkSize));
             checkpoint(State.READ_CHUNK_DELIMITER);
             return chunk;
         }
         case READ_CHUNKED_CONTENT_AS_CHUNKS: {
             assert chunkSize <= Integer.MAX_VALUE;
             int chunkSize = (int) this.chunkSize;
             int readLimit = actualReadableBytes();
 
             // Check if the buffer is readable first as we use the readable byte count
             // to create the HttpChunk. This is needed as otherwise we may end up with
             // create a HttpChunk instance that contains an empty buffer and so is
             // handled like it is the last HttpChunk.
             //
             // See https://github.com/netty/netty/issues/433
             if (readLimit == 0) {
                 return null;
             }
 
             int toRead = chunkSize;
             if (toRead > maxChunkSize) {
                 toRead = maxChunkSize;
             }
             if (toRead > readLimit) {
                 toRead = readLimit;
             }
             HttpChunk chunk = new DefaultHttpChunk(buffer.readBytes(toRead));
             if (chunkSize > toRead) {
                 chunkSize -= toRead;
             } else {
                 chunkSize = 0;
             }
             this.chunkSize = chunkSize;
 
             if (chunkSize == 0) {
                 // Read all content.
                 checkpoint(State.READ_CHUNK_DELIMITER);
             }
 
             if (!chunk.isLast()) {
                 return chunk;
             }
         }
         case READ_CHUNK_DELIMITER: {
             for (;;) {
                 byte next = buffer.readByte();
                 if (next == HttpConstants.CR) {
                     if (buffer.readByte() == HttpConstants.LF) {
                         checkpoint(State.READ_CHUNK_SIZE);
                         return null;
                     }
                 } else if (next == HttpConstants.LF) {
                     checkpoint(State.READ_CHUNK_SIZE);
                     return null;
                 }
             }
         }
         case READ_CHUNK_FOOTER: {
             HttpChunkTrailer trailer = readTrailingHeaders(buffer);
             if (maxChunkSize == 0) {
                 // Chunked encoding disabled.
                 return reset();
             } else {
                 reset();
                 // The last chunk, which is empty
                 return trailer;
             }
         }
         default: {
             throw new Error("Shouldn't reach here.");
         }
 
         }
     }
 
     protected boolean isContentAlwaysEmpty(HttpMessage msg) {
         if (msg instanceof HttpResponse) {
             HttpResponse res = (HttpResponse) msg;
             int code = res.getStatus().getCode();
 
             // Correctly handle return codes of 1xx.
             //
             // See:
             //     - http://www.w3.org/Protocols/rfc2616/rfc2616-sec4.html Section 4.4
             //     - https://github.com/netty/netty/issues/222
             if (code >= 100 && code < 200) {
                 if (code == 101 && !res.containsHeader(HttpHeaders.Names.SEC_WEBSOCKET_ACCEPT)) {
                     // It's Hixie 76 websocket handshake response
                     return false;
                 }
                 return true;
             }
 
             switch (code) {
             case 204: case 205: case 304:
                 return true;
             }
         }
         return false;
     }
 
 
     private Object reset() {
         HttpMessage message = this.message;
         ChannelBuffer content = this.content;
 
         if (content != null) {
             message.setContent(content);
             this.content = null;
         }
         this.message = null;
 
         checkpoint(State.SKIP_CONTROL_CHARS);
         return message;
     }
 
     private static void skipControlCharacters(ChannelBuffer buffer) {
         for (;;) {
             char c = (char) buffer.readUnsignedByte();
             if (!Character.isISOControl(c) &&
                 !Character.isWhitespace(c)) {
                 buffer.readerIndex(buffer.readerIndex() - 1);
                 break;
             }
         }
     }
 
     private Object readFixedLengthContent(ChannelBuffer buffer) {
         //we have a content-length so we just read the correct number of bytes
         long length = HttpHeaders.getContentLength(message, -1);
         assert length <= Integer.MAX_VALUE;
         int toRead = (int) length - contentRead;
         if (toRead > actualReadableBytes()) {
             toRead = actualReadableBytes();
         }
         contentRead += toRead;
         if (length < contentRead) {
             if (!message.isChunked()) {
                 message.setChunked(true);
                 return new Object[] {message, new DefaultHttpChunk(read(buffer, toRead))};
             } else {
                 return new DefaultHttpChunk(read(buffer, toRead));
             }
         }
         if (content == null) {
             content = read(buffer, (int) length);
         } else {
             content.writeBytes(buffer.readBytes((int) length));
         }
         return reset();
     }
 
     /**
      * Try to do an optimized "read" of len from the given {@link ChannelBuffer}.
      *
      * This is part of #412 to safe byte copies
      *
      */
     private ChannelBuffer read(ChannelBuffer buffer, int len) {
         ChannelBuffer internal = internalBuffer();
         if (internal.readableBytes() >= len) {
             int index = internal.readerIndex();
             ChannelBuffer buf = internal.slice(index, len);
 
             // update the readerindex so an the next read its on the correct position
             buffer.readerIndex(index + len);
             return buf;
         } else {
             return buffer.readBytes(len);
         }
     }
 
     private State readHeaders(ChannelBuffer buffer) throws TooLongFrameException {
         headerSize = 0;
         final HttpMessage message = this.message;
         String line = readHeader(buffer);
         String name = null;
         String value = null;
         if (line.length() != 0) {
             message.clearHeaders();
             do {
                 char firstChar = line.charAt(0);
                 if (name != null && (firstChar == ' ' || firstChar == '\t')) {
                     value = value + ' ' + line.trim();
                 } else {
                     if (name != null) {
                         message.addHeader(name, value);
                     }
                     String[] header = splitHeader(line);
                     name = header[0];
                     value = header[1];
                 }
 
                 line = readHeader(buffer);
             } while (line.length() != 0);
 
             // Add the last header.
             if (name != null) {
                 message.addHeader(name, value);
             }
         }
 
         State nextState;
 
         if (isContentAlwaysEmpty(message)) {
             nextState = State.SKIP_CONTROL_CHARS;
         } else if (message.isChunked()) {
             // HttpMessage.isChunked() returns true when either:
             // 1) HttpMessage.setChunked(true) was called or
             // 2) 'Transfer-Encoding' is 'chunked'.
             // Because this decoder did not call HttpMessage.setChunked(true)
             // yet, HttpMessage.isChunked() should return true only when
             // 'Transfer-Encoding' is 'chunked'.
             nextState = State.READ_CHUNK_SIZE;
         } else if (HttpHeaders.getContentLength(message, -1) >= 0) {
             nextState = State.READ_FIXED_LENGTH_CONTENT;
         } else {
             nextState = State.READ_VARIABLE_LENGTH_CONTENT;
         }
         return nextState;
     }
 
     private HttpChunkTrailer readTrailingHeaders(ChannelBuffer buffer) throws TooLongFrameException {
         headerSize = 0;
         String line = readHeader(buffer);
         String lastHeader = null;
         if (line.length() != 0) {
             HttpChunkTrailer trailer = new DefaultHttpChunkTrailer();
             do {
                 char firstChar = line.charAt(0);
                 if (lastHeader != null && (firstChar == ' ' || firstChar == '\t')) {
                     List<String> current = trailer.getHeaders(lastHeader);
                     if (!current.isEmpty()) {
                         int lastPos = current.size() - 1;
                         String newString = current.get(lastPos) + line.trim();
                         current.set(lastPos, newString);
                     } else {
                         // Content-Length, Transfer-Encoding, or Trailer
                     }
                 } else {
                     String[] header = splitHeader(line);
                     String name = header[0];
                     if (!name.equalsIgnoreCase(HttpHeaders.Names.CONTENT_LENGTH) &&
                         !name.equalsIgnoreCase(HttpHeaders.Names.TRANSFER_ENCODING) &&
                         !name.equalsIgnoreCase(HttpHeaders.Names.TRAILER)) {
                         trailer.addHeader(name, header[1]);
                     }
                     lastHeader = name;
                 }
 
                 line = readHeader(buffer);
             } while (line.length() != 0);
 
             return trailer;
         }
 
         return HttpChunk.LAST_CHUNK;
     }
 
     private String readHeader(ChannelBuffer buffer) throws TooLongFrameException {
         StringBuilder sb = new StringBuilder(64);
         int headerSize = this.headerSize;
 
         loop:
         for (;;) {
             char nextByte = (char) buffer.readByte();
             headerSize ++;
 
             switch (nextByte) {
             case HttpConstants.CR:
                 nextByte = (char) buffer.readByte();
                 headerSize ++;
                 if (nextByte == HttpConstants.LF) {
                     break loop;
                 }
                 break;
             case HttpConstants.LF:
                 break loop;
             }
 
             // Abort decoding if the header part is too large.
             if (headerSize >= maxHeaderSize) {
                 // TODO: Respond with Bad Request and discard the traffic
                 //    or close the connection.
                 //       No need to notify the upstream handlers - just log.
                 //       If decoding a response, just throw an exception.
                 throw new TooLongFrameException(
                         "HTTP header is larger than " +
                         maxHeaderSize + " bytes.");
 
             }
 
             sb.append(nextByte);
         }
 
         this.headerSize = headerSize;
         return sb.toString();
     }
 
     protected abstract boolean isDecodingRequest();
     protected abstract HttpMessage createMessage(String[] initialLine) throws Exception;
 
     private static int getChunkSize(String hex) {
         hex = hex.trim();
         for (int i = 0; i < hex.length(); i ++) {
             char c = hex.charAt(i);
             if (c == ';' || Character.isWhitespace(c) || Character.isISOControl(c)) {
                 hex = hex.substring(0, i);
                 break;
             }
         }
 
         return Integer.parseInt(hex, 16);
     }
 
     private static String readLine(ChannelBuffer buffer, int maxLineLength) throws TooLongFrameException {
         StringBuilder sb = new StringBuilder(64);
         int lineLength = 0;
         while (true) {
             byte nextByte = buffer.readByte();
             if (nextByte == HttpConstants.CR) {
                 nextByte = buffer.readByte();
                 if (nextByte == HttpConstants.LF) {
                     return sb.toString();
                 }
             } else if (nextByte == HttpConstants.LF) {
                 return sb.toString();
             } else {
                 if (lineLength >= maxLineLength) {
                     // TODO: Respond with Bad Request and discard the traffic
                     //    or close the connection.
                     //       No need to notify the upstream handlers - just log.
                     //       If decoding a response, just throw an exception.
                     throw new TooLongFrameException(
                             "An HTTP line is larger than " + maxLineLength +
                             " bytes.");
                 }
                 lineLength ++;
                 sb.append((char) nextByte);
             }
         }
     }
 
     private static String[] splitInitialLine(String sb) {
         int aStart;
         int aEnd;
         int bStart;
         int bEnd;
         int cStart;
         int cEnd;
 
         aStart = findNonWhitespace(sb, 0);
         aEnd = findWhitespace(sb, aStart);
 
         bStart = findNonWhitespace(sb, aEnd);
         bEnd = findWhitespace(sb, bStart);
 
         cStart = findNonWhitespace(sb, bEnd);
         cEnd = findEndOfString(sb);
 
         return new String[] {
                 sb.substring(aStart, aEnd),
                 sb.substring(bStart, bEnd),
                 cStart < cEnd? sb.substring(cStart, cEnd) : "" };
     }
 
     private static String[] splitHeader(String sb) {
         final int length = sb.length();
         int nameStart;
         int nameEnd;
         int colonEnd;
         int valueStart;
         int valueEnd;
 
         nameStart = findNonWhitespace(sb, 0);
         for (nameEnd = nameStart; nameEnd < length; nameEnd ++) {
             char ch = sb.charAt(nameEnd);
             if (ch == ':' || Character.isWhitespace(ch)) {
                 break;
             }
         }
 
         for (colonEnd = nameEnd; colonEnd < length; colonEnd ++) {
             if (sb.charAt(colonEnd) == ':') {
                 colonEnd ++;
                 break;
             }
         }
 
         valueStart = findNonWhitespace(sb, colonEnd);
         if (valueStart == length) {
             return new String[] {
                     sb.substring(nameStart, nameEnd),
                     ""
             };
         }
 
         valueEnd = findEndOfString(sb);
         return new String[] {
                 sb.substring(nameStart, nameEnd),
                 sb.substring(valueStart, valueEnd)
         };
     }
 
     private static int findNonWhitespace(String sb, int offset) {
         int result;
         for (result = offset; result < sb.length(); result ++) {
             if (!Character.isWhitespace(sb.charAt(result))) {
                 break;
             }
         }
         return result;
     }
 
     private static int findWhitespace(String sb, int offset) {
         int result;
         for (result = offset; result < sb.length(); result ++) {
             if (Character.isWhitespace(sb.charAt(result))) {
                 break;
             }
         }
         return result;
     }
 
     private static int findEndOfString(String sb) {
         int result;
         for (result = sb.length(); result > 0; result --) {
             if (!Character.isWhitespace(sb.charAt(result - 1))) {
                 break;
             }
         }
         return result;
     }
 }