내 남자의 길~!

Network Working Group                                  S. Josefsson, Ed.
Request for Comments: 3548                                     July 2003
Category: Informational


             The Base16, Base32, and Base64 Data Encodings

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

Abstract

   This document describes the commonly used base 64, base 32, and base
   16 encoding schemes.  It also discusses the use of line-feeds in
   encoded data, use of padding in encoded data, use of non-alphabet
   characters in encoded data, and use of different encoding alphabets.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  2
   2.  Implementation discrepancies . . . . . . . . . . . . . . . . .  2
       2.1.  Line feeds in encoded data . . . . . . . . . . . . . . .  2
       2.2.  Padding of encoded data  . . . . . . . . . . . . . . . .  3
       2.3.  Interpretation of non-alphabet characters in encoded
             data . . . . . . . . . . . . . . . . . . . . . . . . . .  3
       2.4.  Choosing the alphabet  . . . . . . . . . . . . . . . . .  3
   3.  Base 64 Encoding . . . . . . . . . . . . . . . . . . . . . . .  4
   4.  Base 64 Encoding with URL and Filename Safe Alphabet . . . . .  6
   5.  Base 32 Encoding . . . . . . . . . . . . . . . . . . . . . . .  6
   6.  Base 16 Encoding . . . . . . . . . . . . . . . . . . . . . . .  8
   7.  Illustrations and examples . . . . . . . . . . . . . . . . . .  9
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
       9.1.  Normative References . . . . . . . . . . . . . . . . . . 11
       9.2.  Informative References . . . . . . . . . . . . . . . . . 11
   10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11
   11. Editor's Address . . . . . . . . . . . . . . . . . . . . . . . 12
   12. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 13






Josefsson                    Informational                      [Page 1]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


1.  Introduction

   Base encoding of data is used in many situations to store or transfer
   data in environments that, perhaps for legacy reasons, are restricted
   to only US-ASCII [9] data.  Base encoding can also be used in new
   applications that do not have legacy restrictions, simply because it
   makes it possible to manipulate objects with text editors.

   In the past, different applications have had different requirements
   and thus sometimes implemented base encodings in slightly different
   ways.  Today, protocol specifications sometimes use base encodings in
   general, and "base64" in particular, without a precise description or
   reference.  MIME [3] is often used as a reference for base64 without
   considering the consequences for line-wrapping or non-alphabet
   characters.  The purpose of this specification is to establish common
   alphabet and encoding considerations.  This will hopefully reduce
   ambiguity in other documents, leading to better interoperability.

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [1].

2.  Implementation discrepancies

   Here we discuss the discrepancies between base encoding
   implementations in the past, and where appropriate, mandate a
   specific recommended behavior for the future.

2.1.  Line feeds in encoded data

   MIME [3] is often used as a reference for base 64 encoding.  However,
   MIME does not define "base 64" per se, but rather a "base 64
   Content-Transfer-Encoding" for use within MIME.  As such, MIME
   enforces a limit on line length of base 64 encoded data to 76
   characters.  MIME inherits the encoding from PEM [2] stating it is
   "virtually identical", however PEM uses a line length of 64
   characters.  The MIME and PEM limits are both due to limits within
   SMTP.

   Implementations MUST NOT not add line feeds to base encoded data
   unless the specification referring to this document explicitly
   directs base encoders to add line feeds after a specific number of
   characters.








Josefsson                    Informational                      [Page 2]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


2.2.  Padding of encoded data

   In some circumstances, the use of padding ("=") in base encoded data
   is not required nor used.  In the general case, when assumptions on
   size of transported data cannot be made, padding is required to yield
   correct decoded data.

   Implementations MUST include appropriate pad characters at the end of
   encoded data unless the specification referring to this document
   explicitly states otherwise.

2.3.  Interpretation of non-alphabet characters in encoded data

   Base encodings use a specific, reduced, alphabet to encode binary
   data.  Non alphabet characters could exist within base encoded data,
   caused by data corruption or by design.  Non alphabet characters may
   be exploited as a "covert channel", where non-protocol data can be
   sent for nefarious purposes.  Non alphabet characters might also be
   sent in order to exploit implementation errors leading to, e.g.,
   buffer overflow attacks.

   Implementations MUST reject the encoding if it contains characters
   outside the base alphabet when interpreting base encoded data, unless
   the specification referring to this document explicitly states
   otherwise.  Such specifications may, as MIME does, instead state that
   characters outside the base encoding alphabet should simply be
   ignored when interpreting data ("be liberal in what you accept").
   Note that this means that any CRLF constitute "non alphabet
   characters" and are ignored.  Furthermore, such specifications may
   consider the pad character, "=", as not part of the base alphabet
   until the end of the string.  If more than the allowed number of pad
   characters are found at the end of the string, e.g., a base 64 string
   terminated with "===", the excess pad characters could be ignored.

2.4.  Choosing the alphabet

   Different applications have different requirements on the characters
   in the alphabet.  Here are a few requirements that determine which
   alphabet should be used:

   o   Handled by humans.  Characters "0", "O" are easily interchanged,
       as well "1", "l" and "I".  In the base32 alphabet below, where 0
       (zero) and 1 (one) is not present, a decoder may interpret 0 as
       O, and 1 as I or L depending on case.  (However, by default it
       should not, see previous section.)






Josefsson                    Informational                      [Page 3]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


   o   Encoded into structures that place other requirements.  For base
       16 and base 32, this determines the use of upper- or lowercase
       alphabets.  For base 64, the non-alphanumeric characters (in
       particular "/") may be problematic in file names and URLs.

   o   Used as identifiers.  Certain characters, notably "+" and "/" in
       the base 64 alphabet, are treated as word-breaks by legacy text
       search/index tools.

   There is no universally accepted alphabet that fulfills all the
   requirements.  In this document, we document and name some currently
   used alphabets.

3.  Base 64 Encoding

   The following description of base 64 is due to [2], [3], [4] and [5].

   The Base 64 encoding is designed to represent arbitrary sequences of
   octets in a form that requires case sensitivity but need not be
   humanly readable.

   A 65-character subset of US-ASCII is used, enabling 6 bits to be
   represented per printable character.  (The extra 65th character, "=",
   is used to signify a special processing function.)

   The encoding process represents 24-bit groups of input bits as output
   strings of 4 encoded characters.  Proceeding from left to right, a
   24-bit input group is formed by concatenating 3 8-bit input groups.
   These 24 bits are then treated as 4 concatenated 6-bit groups, each
   of which is translated into a single digit in the base 64 alphabet.

   Each 6-bit group is used as an index into an array of 64 printable
   characters.  The character referenced by the index is placed in the
   output string.

















Josefsson                    Informational                      [Page 4]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


                   Table 1: The Base 64 Alphabet

      Value Encoding  Value Encoding  Value Encoding  Value Encoding
          0 A            17 R            34 i            51 z
          1 B            18 S            35 j            52 0
          2 C            19 T            36 k            53 1
          3 D            20 U            37 l            54 2
          4 E            21 V            38 m            55 3
          5 F            22 W            39 n            56 4
          6 G            23 X            40 o            57 5
          7 H            24 Y            41 p            58 6
          8 I            25 Z            42 q            59 7
          9 J            26 a            43 r            60 8
         10 K            27 b            44 s            61 9
         11 L            28 c            45 t            62 +
         12 M            29 d            46 u            63 /
         13 N            30 e            47 v
         14 O            31 f            48 w         (pad) =
         15 P            32 g            49 x
         16 Q            33 h            50 y

   Special processing is performed if fewer than 24 bits are available
   at the end of the data being encoded.  A full encoding quantum is
   always completed at the end of a quantity.  When fewer than 24 input
   bits are available in an input group, zero bits are added (on the
   right) to form an integral number of 6-bit groups.  Padding at the
   end of the data is performed using the '=' character.  Since all base
   64 input is an integral number of octets, only the following cases
   can arise:

   (1) the final quantum of encoding input is an integral multiple of 24
   bits; here, the final unit of encoded output will be an integral
   multiple of 4 characters with no "=" padding,

   (2) the final quantum of encoding input is exactly 8 bits; here, the
   final unit of encoded output will be two characters followed by two
   "=" padding characters, or

   (3) the final quantum of encoding input is exactly 16 bits; here, the
   final unit of encoded output will be three characters followed by one
   "=" padding character.










Josefsson                    Informational                      [Page 5]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


4.  Base 64 Encoding with URL and Filename Safe Alphabet

   The Base 64 encoding with an URL and filename safe alphabet has been
   used in [8].

   An alternative alphabet has been suggested that used "~" as the 63rd
   character.  Since the "~" character has special meaning in some file
   system environments, the encoding described in this section is
   recommended instead.

   This encoding should not be regarded as the same as the "base64"
   encoding, and should not be referred to as only "base64".  Unless
   made clear, "base64" refer to the base 64 in the previous section.

   This encoding is technically identical to the previous one, except
   for the 62:nd and 63:rd alphabet character, as indicated in table 2.

         Table 2: The "URL and Filename safe" Base 64 Alphabet

    Value Encoding  Value Encoding  Value Encoding  Value Encoding
       0 A            17 R            34 i            51 z
       1 B            18 S            35 j            52 0
       2 C            19 T            36 k            53 1
       3 D            20 U            37 l            54 2
       4 E            21 V            38 m            55 3
       5 F            22 W            39 n            56 4
       6 G            23 X            40 o            57 5
       7 H            24 Y            41 p            58 6
       8 I            25 Z            42 q            59 7
       9 J            26 a            43 r            60 8
      10 K            27 b            44 s            61 9
      11 L            28 c            45 t            62 - (minus)
      12 M            29 d            46 u            63 _ (understrike)
      13 N            30 e            47 v
      14 O            31 f            48 w         (pad) =
      15 P            32 g            49 x
      16 Q            33 h            50 y

5.  Base 32 Encoding

   The following description of base 32 is due to [7] (with
   corrections).

   The Base 32 encoding is designed to represent arbitrary sequences of
   octets in a form that needs to be case insensitive but need not be
   humanly readable.





Josefsson                    Informational                      [Page 6]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


   A 33-character subset of US-ASCII is used, enabling 5 bits to be
   represented per printable character.  (The extra 33rd character, "=",
   is used to signify a special processing function.)

   The encoding process represents 40-bit groups of input bits as output
   strings of 8 encoded characters.  Proceeding from left to right, a
   40-bit input group is formed by concatenating 5 8bit input groups.
   These 40 bits are then treated as 8 concatenated 5-bit groups, each
   of which is translated into a single digit in the base 32 alphabet.
   When encoding a bit stream via the base 32 encoding, the bit stream
   must be presumed to be ordered with the most-significant-bit first.
   That is, the first bit in the stream will be the high-order bit in
   the first 8bit byte, and the eighth bit will be the low-order bit in
   the first 8bit byte, and so on.

   Each 5-bit group is used as an index into an array of 32 printable
   characters.  The character referenced by the index is placed in the
   output string.  These characters, identified in Table 2, below, are
   selected from US-ASCII digits and uppercase letters.

                   Table 3: The Base 32 Alphabet

        Value Encoding  Value Encoding  Value Encoding  Value Encoding
            0 A             9 J            18 S            27 3
            1 B            10 K            19 T            28 4
            2 C            11 L            20 U            29 5
            3 D            12 M            21 V            30 6
            4 E            13 N            22 W            31 7
            5 F            14 O            23 X
            6 G            15 P            24 Y         (pad) =
            7 H            16 Q            25 Z
            8 I            17 R            26 2


   Special processing is performed if fewer than 40 bits are available
   at the end of the data being encoded.  A full encoding quantum is
   always completed at the end of a body.  When fewer than 40 input bits
   are available in an input group, zero bits are added (on the right)
   to form an integral number of 5-bit groups.  Padding at the end of
   the data is performed using the "=" character.  Since all base 32
   input is an integral number of octets, only the following cases can
   arise:

   (1) the final quantum of encoding input is an integral multiple of 40
   bits; here, the final unit of encoded output will be an integral
   multiple of 8 characters with no "=" padding,





Josefsson                    Informational                      [Page 7]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


   (2) the final quantum of encoding input is exactly 8 bits; here, the
   final unit of encoded output will be two characters followed by six
   "=" padding characters,

   (3) the final quantum of encoding input is exactly 16 bits; here, the
   final unit of encoded output will be four characters followed by four
   "=" padding characters,

   (4) the final quantum of encoding input is exactly 24 bits; here, the
   final unit of encoded output will be five characters followed by
   three "=" padding characters, or

   (5) the final quantum of encoding input is exactly 32 bits; here, the
   final unit of encoded output will be seven characters followed by one
   "=" padding character.

6.  Base 16 Encoding

   The following description is original but analogous to previous
   descriptions.  Essentially, Base 16 encoding is the standard standard
   case insensitive hex encoding, and may be referred to as "base16" or
   "hex".

   A 16-character subset of US-ASCII is used, enabling 4 bits to be
   represented per printable character.

   The encoding process represents 8-bit groups (octets) of input bits
   as output strings of 2 encoded characters.  Proceeding from left to
   right, a 8-bit input is taken from the input data.  These 8 bits are
   then treated as 2 concatenated 4-bit groups, each of which is
   translated into a single digit in the base 16 alphabet.

   Each 4-bit group is used as an index into an array of 16 printable
   characters.  The character referenced by the index is placed in the
   output string.

                   Table 5: The Base 16 Alphabet

      Value Encoding  Value Encoding  Value Encoding  Value Encoding
          0 0             4 4             8 8            12 C
          1 1             5 5             9 9            13 D
          2 2             6 6            10 A            14 E
          3 3             7 7            11 B            15 F

   Unlike base 32 and base 64, no special padding is necessary since a
   full code word is always available.





Josefsson                    Informational                      [Page 8]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


7.  Illustrations and examples

   To translate between binary and a base encoding, the input is stored
   in a structure and the output is extracted.  The case for base 64 is
   displayed in the following figure, borrowed from [4].

         +--first octet--+-second octet--+--third octet--+
         |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
         +-----------+---+-------+-------+---+-----------+
         |5 4 3 2 1 0|5 4 3 2 1 0|5 4 3 2 1 0|5 4 3 2 1 0|
         +--1.index--+--2.index--+--3.index--+--4.index--+

   The case for base 32 is shown in the following figure, borrowed from
   [6].  Each successive character in a base-32 value represents 5
   successive bits of the underlying octet sequence.  Thus, each group
   of 8 characters represents a sequence of 5 octets (40 bits).

                        1          2          3
          01234567 89012345 67890123 45678901 23456789
         +--------+--------+--------+--------+--------+
         |< 1 >< 2| >< 3 ><|.4 >< 5.|>< 6 ><.|7 >< 8 >|
         +--------+--------+--------+--------+--------+
                                                 <===> 8th character
                                           <====> 7th character
                                      <===> 6th character
                                <====> 5th character
                          <====> 4th character
                     <===> 3rd character
               <====> 2nd character
          <===> 1st character





















Josefsson                    Informational                      [Page 9]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


   The following example of Base64 data is from [4].

       Input data:  0x14fb9c03d97e
       Hex:     1   4    f   b    9   c     | 0   3    d   9    7   e
       8-bit:   00010100 11111011 10011100  | 00000011 11011001
       11111110
       6-bit:   000101 001111 101110 011100 | 000000 111101 100111
       111110
       Decimal: 5      15     46     28       0      61     37     62
       Output:  F      P      u      c        A      9      l      +

       Input data:  0x14fb9c03d9
       Hex:     1   4    f   b    9   c     | 0   3    d   9
       8-bit:   00010100 11111011 10011100  | 00000011 11011001
                                                       pad with 00
       6-bit:   000101 001111 101110 011100 | 000000 111101 100100
       Decimal: 5      15     46     28       0      61     36
                                                          pad with =
       Output:  F      P      u      c        A      9      k      =

       Input data:  0x14fb9c03
       Hex:     1   4    f   b    9   c     | 0   3
       8-bit:   00010100 11111011 10011100  | 00000011
                                              pad with 0000
       6-bit:   000101 001111 101110 011100 | 000000 110000
       Decimal: 5      15     46     28       0      48
                                                   pad with =      =
       Output:  F      P      u      c        A      w      =      =

8.  Security Considerations

   When implementing Base encoding and decoding, care should be taken
   not to introduce vulnerabilities to buffer overflow attacks, or other
   attacks on the implementation.  A decoder should not break on invalid
   input including, e.g., embedded NUL characters (ASCII 0).

   If non-alphabet characters are ignored, instead of causing rejection
   of the entire encoding (as recommended), a covert channel that can be
   used to "leak" information is made possible.  The implications of
   this should be understood in applications that do not follow the
   recommended practice.  Similarly, when the base 16 and base 32
   alphabets are handled case insensitively, alteration of case can be
   used to leak information.

   Base encoding visually hides otherwise easily recognized information,
   such as passwords, but does not provide any computational
   confidentiality.  This has been known to cause security incidents
   when, e.g., a user reports details of a network protocol exchange



Josefsson                    Informational                     [Page 10]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


   (perhaps to illustrate some other problem) and accidentally reveals
   the password because she is unaware that the base encoding does not
   protect the password.

9.  References

9.1.  Normative References

   [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
       Levels", BCP 14, RFC 2119, March 1997.

9.2.  Informative References

   [2] Linn, J., "Privacy Enhancement for Internet Electronic Mail:
       Part I: Message Encryption and Authentication Procedures", RFC
       1421, February 1993.

   [3] Freed, N. and N. Borenstein, "Multipurpose Internet Mail
       Extensions (MIME) Part One: Format of Internet Message Bodies",
       RFC 2045, November 1996.

   [4] Callas, J., Donnerhacke, L., Finney, H. and R. Thayer, "OpenPGP
       Message Format", RFC 2440, November 1998.

   [5] Eastlake, D., "Domain Name System Security Extensions", RFC 2535,
       March 1999.

   [6] Klyne, G. and L. Masinter, "Identifying Composite Media
       Features", RFC 2938, September 2000.

   [7] Myers, J., "SASL GSSAPI mechanisms", Work in Progress.

   [8] Wilcox-O'Hearn, B., "Post to P2P-hackers mailing list", World
       Wide Web http://zgp.org/pipermail/p2p-hackers/2001-
       September/000315.html, September 2001.

   [9] Cerf, V., "ASCII format for Network Interchange", RFC 20, October
       1969.

10.  Acknowledgements

   Several people offered comments and suggestions, including Tony
   Hansen, Gordon Mohr, John Myers, Chris Newman, and Andrew Sieber.
   Text used in this document is based on earlier RFCs describing
   specific uses of various base encodings.  The author acknowledges the
   RSA Laboratories for supporting the work that led to this document.





Josefsson                    Informational                     [Page 11]

RFC 3548     The Base16, Base32, and Base64 Data Encodings     July 2003


11.  Editor's Address

   Simon Josefsson
   EMail: simon@josefsson.org

realloc

동적으로 할당된 메모리를 재할당합니다.

Declaration

void *realloc( void *memblock, size_t size )

Return value

성공 - 새로운 메모리 영역을 가리키는 포인터 반환
실패 - NULL 포인터 반환

Parameters

memblock - NULL 포인터 또는 이전에 할당한 메모리 영역을 가리키는 포인터
size     - 새로 할당받을 메모리 크기(단위는 바이트)

Detail descriptions

realloc()를 번역할 때 "재할당" 또는 "다시 할당"이라고 하는데 많이 어색합니다. 다시 할당하는 것이 아니라 할당된 메모리 영역의 크기를 변경, 대부분은 확장하는 것입니다. 정확하게 이름을 짓는다면 extendalloc()정도가 좋겠습니다. 굳이 "재할당(realloc)"이라고 이름 지은 것은 대부분 새로운 메모리를 할당받기 때문입니다.

 

realloc()에 전달되는 메모리 영역의 크기는 이전에 할당됐던 영역보다 클 수도 있고 작을 수도 있습니다. 대부분 메모리가 부족했기 때문에 다시 할당 받는 것이지만, 작은 경우가 있을 수도 있습니다. 그러나, 작은 경우라면 메모리를 새로 할당할 이유가 없습니다. 메모리가 부족한 경우에 인접해 있는 연속된 구간을 확보할 수 있다면, 다시 말해 현 상태에서 늘릴 수 있는 영역이 있다면 새로 할당하지 않아도 됩니다. 그러나, 대부분은 그렇지가 못하므로 기존 메모리를 해제하고 다른 위치에 할당하게 됩니다. [C 언어 표준에서는 어떻게 할당해야 한다는 것에 대해서는 언급하지 않습니다. 이 모든 상황은 구현에 따라 달라질 수 있습니다.]

메모리를 새로운 위치에 할당하려면 아래 순서에 맞게 작업해야 합니다.

1. 새로운 위치에 지정한 크기만큼 메모리를 할당합니다.
2. 이전 영역에 있던 내용을 새로운 영역에 복사합니다.
3. 이전 영역의 메모리를 해제합니다.

realloc()는 이와 같이 동작합니다. 새로운 영역을 할당받더라도 현재 내용을 잃어버리는 일은 절대 없습니다. realloc()를 흉내낸 코드가 "Example codes" 항목에 있습니다. 참고하기 바랍니다.

그러나, 이와 같은 방식에는 엄청난 결함이 있습니다. realloc()는 새로운 위치에 할당될 수 있기 때문에, 이전 영역을 가리키는 모든 포인터 변수를 새로운 주소로 변경해야 합니다. 그렇게 할 수 없다면 해제된 영역을 가리키는 포인터가 언젠가는 문제를 일으킬 것입니다. 동적으로 할당한 메모리가 있고 여러 개의 포인터가 공유하고 있다면, 절대 realloc()를 사용해서는 안됩니다. 악명높은 덜 떨어진 포인터, 댕글링(dangling) 포인터가 탄생합니다.

realloc()는 어떤 경우를 실패라고 생각할까요? malloc()라면 할당할 메모리가 부족한 경우에 NULL 포인터를 반환합니다. 첫 번째는 확장에 실패한 경우입니다. realloc()의 목적은 메모리를 확장해서 옮기는 것인데, 현재 위치에서뿐만 아니라 새로운 위치로도 옮겨가지 못하면 NULL 포인터를 반환합니다. 이때 이전 영역에 있던 내용은 그대로 남아 있습니다. 두 번째는 새롭게 할당할 크기를 0으로 지정한 경우입니다. 크기가 0이라는 것은 새로운 할당으로 간주하지 않고, 이전에 사용하던 영역의 해제로 봅니다. free() 함수를 호출하는 셈입니다. 사용하던 영역은 해제되어 다음 번 동적 할당에서 사용할 수 있게 되고, NULL 포인터를 반환합니다. NULL 포인터의 반환이 너무 당연한 것이 할당받은 메모리가 없으므로 가리킬 곳도 없습니다. 그러나, 메모리를 해제하기 위해 realloc()를 사용해서는 안됩니다. free()로 해제할 때 가장 분명한 코드가 나오기 때문에 가독성에서 너무 좋지 않은 행동입니다.

memblock 매개 변수에 NULL 포인터를 전달하는 것은 malloc()를 호출하는 것과 같습니다. 사용중인 메모리가 없기 때문에 해제할 메모리도 없고, 결국 할당만 일어나게 되므로 malloc() 호출과 같습니다.

realloc()가 성공할 때의 반환값이 두 가지가 있습니다. 첫 번째는 현재 위치에서 확장에 성공한 경우로, memblock 매개 변수에 전달된 주소와 같습니다. 두 번째는 연속된 메모리가 없어서 새로운 위치에 할당된 경우로 memblock 매개 변수와 다른 주소입니다. 주의해야 할 것이 있다면 현재 위치에서 확장될 수 있다고 생각하는 것입니다. 함수 이름이 주는 모호함 때문에 자칫 엄청난 실수를 할 수 있습니다.

간혹 realloc()가 필요한지 의아할 때가 있습니다. 메모리가 부족한 상황을 만나기 전에 리스트(list) 자료구조를 사용하거나 엄청난 크기로 할당한 다음 나누어 쓰는 방법이 있습니다. 동적으로 할당한 메모리를 여러 개의 포인터 변수가 가리키는 상황이 생길 수 있다면, 지금 얘기한 방법들을 진지하게 고민해야 할 것입니다.

Remarks

메모리 동적 할당 함수인 calloc(), malloc(), realloc()를 비교한 표가 malloc()에 있습니다. 참고하기 바랍니다.

Header files

<stdlib.h>   <malloc.h>

Example codes

1. realloc()로 메모리를 "확장"하거나 "축소"할 때 발생하는 포인터 변화를 보여줍니다.
2. 먼저 NULL 포인터를 전달해서 메모리를 할당한 다음, 사용중인 크기보다 두 배 크게 "확장"하고, 최초 크기보다 두 배 작게 "축소"해서 결과를 비교합니다.
3. 출력 결과를 보면 "확장"할 때는 반환된 주소가 사용중인 주소와 다르지만, "축소"할 때는 사용중인 주소와 같습니다. "축소"할 때는 사용중인 메모리를 재활용하고 있음을 알 수 있습니다.
4. 그러나, C 언어 표준에서는 재활용할 것을 요구하지 않습니다. 컴파일러를 구현하는 회사측에서 어떻게 구현할지 결정할 따름입니다.
5. free()는 한번만 사용했습니다. realloc()를 세 번 호출했지만, 두 번째 호출부터는 내부적으로 free()를 호출하기 때문에 realloc() 호출 횟수만큼 free()를 호출해서는 안됩니다.

#include <stdio.h> #include <stdlib.h> void main() {     int* array = NULL;     const int size = 5;     array = realloc( NULL, size*sizeof(int) );     printf( "[확장]\n" );     printf( "old - %d\n", array );     array = realloc( array, size*sizeof(int)*2 );     printf( "cur - %d\n", array );     printf( "\n[축소]\n" );     printf( "old - %d\n", array );     array = realloc( array, size*sizeof(int)/2 );     printf( "cur - %d\n", array );     free( array ); } [출력 결과] [확장] old - 4397872 cur - 4397776 [축소] old - 4397776 cur - 4397776

1. realloc()의 기본 사용법을 보여줍니다.
2. NULL 포인터를 전달해서 malloc()처럼 사용하는 방법과 사용중인 메모리를 두 배로 확장했을 때의 결과를 보여줍니다.
3. malloc()처럼 바이트 단위로 동작하기 때문에 요소 개수와 요소 크기를 곱해서 전달합니다.
4. 출력 결과를 보면, 사용중인 메모리를 20바이트에서 40바이트로 확장하면 사용중인 영역이 확장되는 것이 아니라 새로운 영역에 내용을 복사합니다. 사용중인 영역의 내용은 손상없이 복사되지만, 확장된 영역은 초기화되지 않고 쓰레기로 채워집니다.
5. 동적 배열을 하나만 사용하고 크기도 20바이트를 확장했을 뿐인데, 새로운 주소를 반환한다는 것은 사용중인 영역의 연속된 구간을 할당하는 것이 얼마나 어려운지 보여줍니다. 출력 결과에서 []로 감싼 숫자가 할당받은 주소인데 서로 다릅니다. 절대 사용중인 주소를 계속해서 사용할 수 있을 거라고 기대해선 안됩니다.
6. MultiArray()는 배열을 초기화하는 함수로, 0부터 시작해서 multi의 배수로 채웁니다.

#include <stdio.h> #include <stdlib.h> void MultiArray( int* array, int size, int multi ); void ShowArray( int* array, int size ); void main() {     int* array = NULL;     int  size = 5;     array = realloc( NULL, size*sizeof(int) );     MultiArray( array, size, 3 );     ShowArray( array, size );     size *= 2;     array = realloc( array, size*sizeof(int) );     ShowArray( array, size );     free( array ); } void MultiArray( int* array, int size, int multi ) {     int i;     for( i = 0; i < size; i++ )         array[i] = i*multi; } void ShowArray( int* array, int size ) {     int i;     printf( "[%d]", array );     for( i = 0; i < size; i++ )         printf( " %d", array[i] );     printf( "\n" ); } [출력 결과] [4397776] 0 3 6 9 12 [4397680] 0 3 6 9 12 -842150451 -842150451 -842150451 -842150451 -842150451

1. 사용중인 메모리의 크기를 늘려주는 realloc()를 만들어 봅니다. ExtendArray() 내부에서 calloc()로 새로 만든 메모리를 초기화합니다. 프로그램은 0보다 작거나 같은 정수를 입력하면 종료합니다.
2. realloc()와 똑같이 만드는 것은 불가능합니다. 간단하게 realloc()의 특징일 수 있는 것만을 일부 구현합니다.
3. realloc()를 호출하는 상황이 네 가지 있습니다. 이들 네 가지는 "최초 할당"과 "축소", "확장", "변화 없음"으로 부를 수 있습니다.
4. "최초 할당"은 사용중인 메모리 주소 대신 NULL 포인터가 전달되는 경우로, 사용중인 메모리가 없다는 뜻이므로 별도의 코드없이 calloc()의 호출 결과를 반환합니다.
5. "축소"와 "변화 없음"은 메모리 크기를 줄이는 것인데, 굳이 사용중인 메모리를 해제할 필요없이 기존에 사용하던 메모리를 재활용합니다. 크기를 줄이는 과정에서 남는 메모리를 해제할 수 있는 방법이 없으므로, 사용중이던 메모리를 해제할 때까지 그대로 둡니다. 일종의 낭비라고 생각할 수도 있겠습니다. ExtendArray() 내부적으로 메모리에 변화가 없으므로 매개 변수로 전달된 oldblock을 그대로 반환합니다.
6. "확장"일 때 realloc()를 가장 많이 사용합니다. 연속된 메모리가 있다고 보장할 수 없기 때문에, 요청한 메모리를 새롭게 할당합니다. 사용중인 메모리의 내용을 새로운 메모리로 옮기고, 사용중인 메모리를 해제합니다.
7. calloc()를 사용했으므로 "확장"된 메모리는 모두 0으로 초기화됩니다. 마지막 출력 결과를 보면, 요소가 3개에서 6개로 확장되었고, 확장된 요소에는 0이 들어갑니다. calloc()를 사용해서 할당했다는 증거입니다. 실제의 realloc()는 "확장" 메모리를 초기화하지 않는데, malloc()을 사용하는 것 같습니다.
8. 출력 결과를 분석하기가 조금 어렵습니다. 첫 번째 결과는 "최초 할당"이고, 두 번째 결과는 "확장"이고 FillArray()를 호출했기 때문에 새로운 내용으로 채워졌습니다. 세 번째와 네 번째 결과는 "축소"이고, "축소"는 사용중이던 메모리를 해제하지 않기 때문에 이전 결과와 똑같이 나옵니다.
9. FillArray()는 메모리를 확장할 때만 호출합니다. "축소"에서 사용중인 메모리를 유지한다는 것을 보여주기 위해 FillArray()는 "확장"일 때만 호출합니다. 그러나, "확장"에 대한 결과도 보여줘야 하므로 반복문을 벗어나면 무조건 2배로 확장합니다. 확장 메모리가 0으로 초기화된다는 것을 보여주기 위해, 이번에는 FillArray()를 호출하지 않습니다.
10. 의도적으로 calloc()를 사용했지만, 메모리를 초기화하지 않는 malloc()를 사용해도 괜찮습니다.
11. FillArray()와 ShowArray()는 배열을 난수로 채우고 화면에 출력하는 함수들입니다. 대단할 것이 없는 함수이므로 설명은 생략합니다.

#include <stdio.h> #include <stdlib.h> #include <string.h> void* ExtendArray( void* p, int cur, int want, int datasize ); void FillArray( int* array, int size ); void ShowArray( int* array, int size ); void main() {     int* array = NULL;     int  want, use = 0;     while( 1 )     {         printf( "개수 : " );         scanf( "%d", &want );         if( want <= 0 )             break;         array = ExtendArray( array, use, want, sizeof(int) );         if( want > use )             FillArray( array, want );         use = want;         ShowArray( array, use );     }     printf( "[calloc() 확인]\n" );     want = use * 2;     array = ExtendArray( array, use, want, sizeof(int) );     ShowArray( array, want ); } void* ExtendArray( void* oldblock, int count, int want, int datasize ) {     void* block;     if( oldblock == NULL )                 // 최초 할당         return calloc( want, datasize );     if( count >= want )                    // 축소, 변화 없음         block = oldblock;     else                                   // 확장     {         block = calloc( want, datasize );         memcpy( block, oldblock, count*datasize );         free( oldblock );     }     return block; } void FillArray( int* array, int size ) {     int i;     for( i = 0; i < size; i++ )         array[i] = rand()%100; } void ShowArray( int* array, int size ) {     int i;     for( i = 0; i < size; i++ )         printf( "%d ", array[i] );     printf( "\n" ); } [출력 결과] 개수 : 4 41 67 34 0 개수 : 9 69 24 78 58 62 64 5 45 81 개수 : 7 69 24 78 58 62 64 5 개수 : 3 69 24 78 개수 : 0 [calloc() 확인] 69 24 78 0 0 0

보통 함수 선언 앞에도 static을 붙일수 있습니다.

원래 static은 전역 변수를 선언할 때 많이 사용되는데

함수 앞에 static을 선언하면...

이 함수가 선언된 파일 안에서만 함수를 호출할 수 있다는 의미가 됩니다.

따라서 파일 3개에서 다음과 같은 사용이 가능해 지네요.

a.c  파일

static void func1(void)

{

    ......

}

b.c 파일

void func1(void)

{

    ......

}

main.c 파일

extern void func1(void)

void main(void)

{

    func1();

    ......

}

원래 static으로 선언되지 않았으면 전체 프로젝트에서 같은 이름의 함수 func1()이 2개나 선언되었기 때문에 컴파일 에러가 발생합니다.

그러나 위처럼 a.c 파일의 func1()은 static으로 선언되면 컴파일 에러가 발생하지 않습니다.

단 a.c 파일의 func1()은 a.c 파일에서만 효력을 가지게 되며, 당연히 a.c 파일에서 호출하는 func1()은 a.c 파일에 선언된 함수를 Call 하는 것이고

main.c 처럼 다른 파일에서 호출하는 func1()은 b.c 파일에서 선언된 func1()을 사용하게 됩니다.

그런데 이거 여러사람이 작업할 때, 헷갈리면 정말 골때리는 경우도 나오겠네요.

모 디버깅을 하면 바로 알겠지만...

이클립스 환경에서 로보코드 로봇을 빌드하려면, 먼저 프로젝트를 만들어야 합니다.

1. File->New->Project 에서 프로젝트를 만듭니다.

자바 프로그램이기 때문에 그냥 "Java Project" 를 선택해줍니다.

Finish 버튼은 절대 누르지 마시고, Next 를 누릅니다.

이제 프로젝트 세팅을 할 차례입니다. robocode 패키지 안에는 라이브러리, JAVADoc 이 있기 떄문에
이것들도 링크를 해줘야 합니다.(뭐 JAVADOC 이 머리속에 있다면 라이브러리만 링크해줘도 상관 없습니다.)

위 화면처럼 만든 후 Add External JARs.... 를 클릭합니다.

로보코드가 설치되있는 폴더로 찾아가 robocode.jar 을 엽니다.


이제 Javadoc 을 세팅해줄 시간입니다.

Javadoc Location 에서  Edit 를 누르고

Browse를 이용해서 해당 경로를 지정해주거나, 경로를 외고 있다면 위 형식에 맞게 지정해주면 끝!!

이제 탱크를 만들 수 있습니다.

난이도 : 초급

McCoy David, Writer, Independent

2007 년 4 월 17 일

코너에 갇히거나 원하는 이동 방향에서 너무 많이 벗어나지 않으면서, 로봇과 벽 사이의 간격을 유지하는 알고리즘은 간단히 만들 수 없는 것 같습니다. 한 가지 간단한 솔루션으로, Factored wall avoidance가 있습니다. 이 글에서, David McCoy가 이를 구현하는 방법을 설명합니다.

With a few additions to the bot we built in "상대편의 움직임 추적하기"에서 구현했던 로봇에 몇 가지를 더 추가하여, 기존의 움직임 알고리즘 또는 문제가 많은 움직임 알고리즘에 Factored Wall Avoidance를 추가할 수 있다. Factored Wall Avoidance는 자신의 로봇과 벽의 근접성에 따라서 안전한 방향 설정(heading)으로 원하는 방향을 팩토링 함으로써 최상의 방향을 찾는 것이다.

일반 수학적 계산에 헬퍼 메소드 추가하기

우선 자주 사용되는 수학적 알고리즘에 헬퍼 메소드를 로봇에 추가한다.

calculateBearingToXYRadians() 메소드는 java.lang.Math 메소드 atan2()를 사용하여 sourceX,sourceY에서 targetX,targetY까지 절대 위치(absolute bearing)를 계산한 다음, 이 값을 sourceHeading에 관련된 위치로 변환한다.

그리고 normalizeAbsoluteAngleRadians() 메소드와 normalizeRelativeAngleRadians() 메소드도 필요하다.

Listing 1. 수학 헬퍼 메소드

private static final double DOUBLE_PI = (Math.PI * 2); private static final double HALF_PI = (Math.PI / 2); public double calculateBearingToXYRadians(double sourceX, double sourceY, double sourceHeading, double targetX, double targetY) { return normalizeRelativeAngleRadians( Math.atan2((targetX - sourceX), (targetY - sourceY)) - sourceHeading); } public double normalizeAbsoluteAngleRadians(double angle) { if (angle < 0) { return (DOUBLE_PI + (angle % DOUBLE_PI)); } else { return (angle % DOUBLE_PI); } } public static double normalizeRelativeAngleRadians(double angle) { double trimmedAngle = (angle % DOUBLE_PI); if (trimmedAngle > Math.PI) { return -(Math.PI - (trimmedAngle % Math.PI)); } else if (trimmedAngle < -Math.PI) { return (Math.PI + (trimmedAngle % Math.PI)); } else { return trimmedAngle; } }

위로

AdvancedRobot을 back-as-front 기능으로 확장하기

다음으로, 로봇을 반대로 이동시키기 위한 back-as-front 기능을 제공하기 위해 AdvancedRobot 클래스 기능을 몇 가지 헬퍼 메소드로 확장할 필요가 있다.

• getRelativeHeading() 메소드는 로봇의 현재 위치와 관련하여 정확한 방향을 계산한다.
  
  
• reverseDirection() 메소드는 매우 단순하다. direction 인스턴스 변수를 토글링(toggle) 하고 로봇의 방향을 바꾼다. 감속할 때에는 시간이 걸리기 때문에 로봇은 속도에 따라서, 방향을 바꾸기 전에 최대 네 개의 프레임까지 같은 방향으로 움직일 수도 있다.
  
  
• setAhead()와 setBack() 메소드는 AdvancedRobot 클래스에서 같은 이름의 메소드를 오버라이드 한다. 현재 방향에 대한 로봇의 속도를 설정하고, direction 인스턴스 변수를 필요에 따라 조정한다. 비례 연산은 로봇이 현재 움직이고 있는 방향과 관련이 있다.
  
  
• setTurnLeftRadiansOptimal()과 setTurnRightRadiansOptimal() 메소드는 (Math.PI / 2) 보다 크게 회전하여 로봇의 방향을 바꾼다. adjustHeadingForWalls 메소드를 사용할 때 이러한 메소드들을 사용해야 하는데, 나중에 설명하겠다.
  
  

주: getter와 setter 메소드를 사용하는 대신 direction 인스턴스 변수에 직접 액세스 한다. 이것은 좋은 방법은 아니지만, 나는 내 로봇 코드에 이를 수행하여 데이터 액세스 속도를 높이곤 한다.

Listing 2. 로봇 헬퍼 메소드

public double getRelativeHeadingRadians() { double relativeHeading = getHeadingRadians(); if (direction < 1) { relativeHeading = normalizeAbsoluteAngleRadians(relativeHeading + Math.PI); } return relativeHeading; } public void reverseDirection() { double distance = (getDistanceRemaining() * direction); direction *= -1; setAhead(distance); } public void setAhead(double distance) { double relativeDistance = (distance * direction); super.setAhead(relativeDistance); if (distance < 0) { direction *= -1; } } public void setBack(double distance) { double relativeDistance = (distance * direction); super.setBack(relativeDistance); if (distance > 0) { direction *= -1; } } public void setTurnLeftRadiansOptimal(double angle) { double turn = normalizeRelativeAngleRadians(angle); if (Math.abs(turn) > HALF_PI) { reverseDirection(); if (turn < 0) { turn = (HALF_PI + (turn % HALF_PI)); } else if (turn > 0) { turn = -(HALF_PI - (turn % HALF_PI)); } } setTurnLeftRadians(turn); } public void setTurnRightRadiansOptimal(double angle) { double turn = normalizeRelativeAngleRadians(angle); if (Math.abs(turn) > HALF_PI) { reverseDirection(); if (turn < 0) { turn = (HALF_PI + (turn % HALF_PI)); } else if (turn > 0) { turn = -(HALF_PI - (turn % HALF_PI)); } } setTurnRightRadians(turn); }

위로

Factored Wall Avoidance 추가하기

소셜 북마크 mar.gar.in Digg del.icio.us Slashdot

우리가 추가할 마지막 메소드는 adjustHeadingForWalls()이다.

이 메소드의 초반부는 벽과의 근접성에 기반하여 안전한 x,y 위치를 선택한다. (이것은 로봇의 현재 x 또는 y 좌표 또는 로봇이 벽에 가까이 있을 경우 중심점이 될 것이다.) 이 메소드의 후반부는 "안전한" 방향을 계산하고 로봇이 벽에 얼마나 근접해 있는가에 비례하여 원하는 방향으로 이를 팩토링 한다.

로봇이 벽으로 나아가는 정도는 WALL_AVOID_INTERVAL과 WALL_AVOID_FACTORS 상수를 사용하여 조정될 수 있다.

Listing 3. 벽 피하기 메소드

private static final double WALL_AVOID_INTERVAL = 10; private static final double WALL_AVOID_FACTORS = 20; private static final double WALL_AVOID_DISTANCE = (WALL_AVOID_INTERVAL * WALL_AVOID_FACTORS); private double adjustHeadingForWalls(double heading) { double fieldHeight = getBattleFieldHeight(); double fieldWidth = getBattleFieldWidth(); double centerX = (fieldWidth / 2); double centerY = (fieldHeight / 2); double currentHeading = getRelativeHeadingRadians(); double x = getX(); double y = getY(); boolean nearWall = false; double desiredX; double desiredY; // If we are too close to a wall, calculate a course toward // the center of the battlefield. if ((y < WALL_AVOID_DISTANCE) || ((fieldHeight - y) < WALL_AVOID_DISTANCE)) { desiredY = centerY; nearWall = true; } else { desiredY = y; } if ((x < WALL_AVOID_DISTANCE) || ((fieldWidth - x) < WALL_AVOID_DISTANCE)) { desiredX = centerX; nearWall = true; } else { desiredX = x; } // Determine the safe heading and factor it in with the desired // heading if the bot is near a wall if (nearWall) { double desiredBearing = calculateBearingToXYRadians(x, y, currentHeading, desiredX, desiredY); double distanceToWall = Math.min( Math.min(x, (fieldWidth - x)), Math.min(y, (fieldHeight - y))); int wallFactor = (int)Math.min((distanceToWall / WALL_AVOID_INTERVAL), WALL_AVOID_FACTORS); return ((((WALL_AVOID_FACTORS - wallFactor) * desiredBearing) + (wallFactor * heading)) / WALL_AVOID_FACTORS); } else { return heading; } }

위로

결론

나머지는 쉽다. 현재의 네비게이션 알고리즘을 사용하고 adjustHeadingForWalls() 메소드를 통해 그 결과를 제공함으로써 벽을 피할 수 있다.

단순하게 하기 위해 로봇 예제(다운로드)는 방향 변경에 0을 요청하여 직선 라인으로 움직일 것이다.

Listing 4. 벽 피하기 메소드

public void run() { while(true) { setTurnRightRadiansOptimal(adjustHeadingForWalls(0)); setAhead(100); execute(); } }

이제 다 되었다. 간단하지만, 효과적이다.
<출처: http://www.ibm.com/developerworks/kr/library/j-fwa/>