Network Working Group G. Zorn Request for Comments: 2433 S. Cobb Category: Informational Microsoft Corporation October 1998 Microsoft PPP CHAP Extensions 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 (1998). All Rights Reserved. IESG Note The protocol described here has significant vulnerabilities. People planning on implementing or using this protocol should read section 12, "Security Considerations". 1. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method for transporting multi-protocol datagrams over point-to-point links. PPP defines an extensible Link Control Protocol and a family of Network Control Protocols (NCPs) for establishing and configuring different network-layer protocols. This document describes Microsoft's PPP CHAP dialect (MS-CHAP), which extends the user authentication functionality provided on Windows networks to remote workstations. MS-CHAP is closely derived from the PPP Challenge Handshake Authentication Protocol described in RFC 1994 [2], which the reader should have at hand. The algorithms used in the generation of various MS-CHAP protocol fields are described in an appendix. 2. Introduction Microsoft created MS-CHAP to authenticate remote Windows workstations, providing the functionality to which LAN-based users are accustomed while integrating the encryption and hashing algorithms used on Windows networks. Zorn & Cobb Informational [Page 1] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Where possible, MS-CHAP is consistent with standard CHAP. Briefly, the differences between MS-CHAP and standard CHAP are: * MS-CHAP is enabled by negotiating CHAP Algorithm 0x80 in LCP option 3, Authentication Protocol. * The MS-CHAP Response packet is in a format designed for compatibility with Microsoft's Windows NT 3.5, 3.51 and 4.0, and Windows95 networking products. The MS-CHAP format does not require the authenticator to store a clear-text or reversibly encrypted password. * MS-CHAP provides authenticator-controlled authentication retry and password changing mechanisms. * MS-CHAP defines a set of reason-for-failure codes returned in the Failure packet Message field. 3. Specification of Requirements In this document, the key words "MAY", "MUST, "MUST NOT", "optional", "recommended", "SHOULD", and "SHOULD NOT" are to be interpreted as described in [2]. 4. LCP Configuration The LCP configuration for MS-CHAP is identical to that for standard CHAP, except that the Algorithm field has value 0x80, rather than the MD5 value 0x05. PPP implementations which do not support MS-CHAP, but correctly implement LCP Config-Rej, should have no problem dealing with this non-standard option. 5. Challenge Packet The MS-CHAP Challenge packet is identical in format to the standard CHAP Challenge packet. MS-CHAP authenticators send an 8-octet challenge Value field. Peers need not duplicate Microsoft's algorithm for selecting the 8-octet value, but the standard guidelines on randomness [1,2,7] SHOULD be observed. Microsoft authenticators do not currently provide information in the Name field. This may change in the future. Zorn & Cobb Informational [Page 2] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 6. Response Packet The MS-CHAP Response packet is identical in format to the standard CHAP Response packet. However, the Value field is sub-formatted differently as follows: 24 octets: LAN Manager compatible challenge response 24 octets: Windows NT compatible challenge response 1 octet : "Use Windows NT compatible challenge response" flag The LAN Manager compatible challenge response is an encoded function of the password and the received challenge as output by the routine LmChallengeResponse() (see section A.1, below). LAN Manager passwords are limited to 14 case-insensitive OEM characters. Note that use of the LAN Manager compatible challenge response has been deprecated; peers SHOULD NOT generate it, and the sub-field SHOULD be zero-filled. The algorithm used in the generation of the LAN Manager compatible challenge response is described here for informational purposes only. The Windows NT compatible challenge response is an encoded function of the password and the received challenge as output by the routine NTChallengeResponse() (see section A.5, below). The Windows NT password is a string of 0 to (theoretically) 256 case-sensitive Unicode [8] characters. Current versions of Windows NT limit passwords to 14 characters, mainly for compatibility reasons; this may change in the future. The "use Windows NT compatible challenge response" flag, if 1, indicates that the Windows NT response is provided and should be used in preference to the LAN Manager response. The LAN Manager response will still be used if the account does not have a Windows NT password hash, e.g. if the password has not been changed since the account was uploaded from a LAN Manager 2.x account database. If the flag is 0, the Windows NT response is ignored and the LAN Manager response is used. Since the use of LAN Manager authentication has been deprecated, this flag SHOULD always be set (1) and the LAN Manager compatible challenge response field SHOULD be zero-filled. The Name field identifies the peer's user account name. The Windows NT domain name may prefix the user's account name (e.g. "BIGCO\johndoe" where "BIGCO" is a Windows NT domain containing the user account "john-doe"). If a domain is not provided, the backslash should also be omitted, (e.g. "johndoe"). Zorn & Cobb Informational [Page 3] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 7. Success Packet The Success packet is identical in format to the standard CHAP Success packet. 8. Failure Packet The Failure packet is identical in format to the standard CHAP Failure packet. There is, however, formatted text stored in the Message field which, contrary to the standard CHAP rules, affects the protocol. The Message field format is: "E=eeeeeeeeee R=r C=cccccccccccccccc V=vvvvvvvvvv" where The "eeeeeeeeee" is the decimal error code (need not be 10 digits) corresponding to one of those listed below, though implementations should deal with codes not on this list gracefully. 646 ERROR_RESTRICTED_LOGON_HOURS 647 ERROR_ACCT_DISABLED 648 ERROR_PASSWD_EXPIRED 649 ERROR_NO_DIALIN_PERMISSION 691 ERROR_AUTHENTICATION_FAILURE 709 ERROR_CHANGING_PASSWORD The "r" is a flag set to "1" if a retry is allowed, and "0" if not. When the authenticator sets this flag to "1" it disables short timeouts, expecting the peer to prompt the user for new credentials and resubmit the response. The "cccccccccccccccc" is 16 hexadecimal digits representing an ASCII representation of a new challenge value. This field is optional. If it is not sent, the authenticator expects the resubmitted response to be calculated based on the previous challenge value plus decimal 23 in the first octet, i.e. the one immediately following the Value Size field. Windows 95 authenticators may send this field. Windows NT authenticators do not, but may in the future. Both systems implement peer support of this field. The "vvvvvvvvvv" is the decimal version code (need not be 10 digits) indicating the MS-CHAP protocol version supported on the server. Currently, this is interesting only in selecting a Change Password packet type. If the field is not present the version should be assumed to be 1; since use of the version 1 Zorn & Cobb Informational [Page 4] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Change Password packet has been deprecated, this field SHOULD always contain a value greater than or equal to 2. Implementations should accept but ignore additional text they do not recognize. 9. Change Password Packet (version 1) The version 1 Change Password packet does not appear in standard CHAP. It allows the peer to change the password on the account specified in the previous Response packet. The version 1 Change Password packet should be sent only if the authenticator reports ERROR_PASSWD_EXPIRED (E=648) and V is either missing or equal to one in the Message field of the Failure packet. The use of the Change Password Packet (version 1) has been deprecated; the format of the packet is described here for informational purposes, but peers SHOULD NOT transmit it. The format of this packet is as follows: 1 octet : Code (=5) 1 octet : Identifier 2 octets: Length (=72) 16 octets: Encrypted LAN Manager Old password Hash 16 octets: Encrypted LAN Manager New Password Hash 16 octets: Encrypted Windows NT Old Password Hash 16 octets: Encrypted Windows NT New Password Hash 2 octets: Password Length 2 octets: Flags Code 5 Identifier The Identifier field is one octet and aids in matching requests and replies. The value is the Identifier of the received Failure packet to which this packet responds plus 1. Length 72 Encrypted LAN Manager New Password Hash Encrypted LAN Manager Old Password Hash These fields contain the LAN Manager password hash of the new and old passwords encrypted with the last received challenge value, as output by the routine LmEncryptedPasswordHash() (see section A.8, below). Zorn & Cobb Informational [Page 5] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Encrypted Windows NT New Password Hash Encrypted Windows NT Old Password Hash These fields contain the Windows NT password hash of the new and old passwords encrypted with the last received challenge value, as output by the pseudo-code routine NtEncryptedPasswordHash() (see section A.10, below). Password Length The length in octets of the LAN Manager compatible form of the new password. If this value is greater than or equal to zero and less than or equal to 14 it is assumed that the encrypted LAN Manager password hash fields are valid. Otherwise, it is assumed these fields are not valid, in which case the Windows NT compatible passwords MUST be provided. Flags This field is two octets in length. It is a bit field of option flags where 0 is the least significant bit of the 16-bit quantity: Bit 0 If this bit is set (1), it indicates that the encrypted Windows NT hashed passwords are valid and should be used. If this bit is cleared (0), the Windows NT fields are not used and the LAN Manager fields must be provided. Bits 1-15 Reserved, always clear (0). 10. Change Password Packet (version 2) The version 2 Change Password packet does not appear in standard CHAP. It allows the peer to change the password on the account specified in the preceding Response packet. The version 2 Change Password packet should be sent only if the authenticator reports ERROR_PASSWD_EXPIRED (E=648) and a version of 2 or greater in the Message field of the Failure packet. This packet type is supported by Windows NT 3.51, 4.0 and recent versions of Windows 95. It is not supported by Windows NT 3.5 or early versions of Windows 95. The format of this packet is as follows: 1 octet : Code 1 octet : Identifier 2 octets : Length 516 octets : Password Encrypted with Old NT Hash Zorn & Cobb Informational [Page 6] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 16 octets : Old NT Hash Encrypted with New NT Hash 516 octets : Password Encrypted with Old LM Hash 16 octets : Old LM Hash Encrypted With New NT Hash 24 octets : LAN Manager compatible challenge response 24 octets : Windows NT compatible challenge response 2-octet : Flags Code 6 Identifier The Identifier field is one octet and aids in matching requests and replies. The value is the Identifier of the received Failure packet to which this packet responds plus 1. Length 1118 Password Encrypted with Old NT Hash This field contains the PWBLOCK form of the new Windows NT password encrypted with the old Windows NT password hash, as output by the NewPasswordEncryptedWithOldNtPasswordHash() routine (see section A.11, below). Old NT Hash Encrypted with New NT Hash This field contains the old Windows NT password hash encrypted with the new Windows NT password hash, as output by the OldNtPasswordHashEncryptedWithNewNtPasswordHash() routine (see section A.14, below). Password Encrypted with Old LM Hash This field contains the PWBLOCK form of the new Windows NT password encrypted with the old LAN Manager password hash, as output by the NewPasswordEncryptedWithOldLmPasswordHash() routine described in section A.15, below. Note, however, that the use of this field has been deprecated: peers SHOULD NOT generate it, and this field SHOULD be zero-filled. Old LM Hash Encrypted With New NT Hash This field contains the old LAN Manager password hash encrypted with the new Windows NT password hash, as output by the OldLmPasswordHashEncryptedWithNewNtPasswordHash() routine (see section A.16, below). Note, however, that the use of this field has been deprecated: peers SHOULD NOT generate it, and this field SHOULD be zero-filled. Zorn & Cobb Informational [Page 7] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 LAN Manager compatible challenge response Windows NT compatible challenge response The challenge response field (as described in the Response packet description), but calculated on the new password and the same challenge used in the last response. Note that use of the LAN Manager compatible challenge response has been deprecated; peers SHOULD NOT generate it, and the field SHOULD be zero- filled. Flags This field is two octets in length. It is a bit field of option flags where 0 is the least significant bit of the 16-bit quantity. The format of this field is illustrated in the following diagram: 1 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bit 0 The "use Windows NT compatible challenge response" flag as described in the Response packet. Bit 1 Set (1) indicates that the "Password Encrypted with Old LM Hash" and "Old LM Hash Encrypted With New NT Hash" fields are valid and should be used. Clear (0) indicates these fields are not valid. This bit SHOULD always be clear (0). Bits 2-15 Reserved, always clear (0). 11. Security Considerations As an implementation detail, the authenticator SHOULD limit the number of password retries allowed to make brute-force password guessing attacks more difficult. Because the challenge value is encrypted using the password hash to form the response and the challenge is transmitted in clear-text form, both passive known-plaintext and active chosen-plaintext attacks against the password hash are possible. Suitable precautions (i.e., frequent password changes) SHOULD be taken in environments where eavesdropping is likely. Zorn & Cobb Informational [Page 8] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 The Change Password (version 1) packet is vulnerable to a passive eavesdropping attack which can easily reveal the new password hash. For this reason, it MUST NOT be sent if eavesdropping is possible. 12. References [1] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, July 1994. [2] Simpson, W., "PPP Challenge Handshake Authentication Protocol (CHAP)", RFC 1994, August 1996. [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [4] "Data Encryption Standard (DES)", Federal Information Processing Standard Publication 46-2, National Institute of Standards and Technology, December 1993. [5] Rivest, R., "MD4 Message Digest Algorithm", RFC 1320, April 1992. [6] RC4 is a proprietary encryption algorithm available under license from RSA Data Security Inc. For licensing information, contact: RSA Data Security, Inc. 100 Marine Parkway Redwood City, CA 94065-1031 [7] Eastlake, D., Crocker, S., and J. Schiller, "Randomness Recomnendations for Security", RFC 1750, December 1994. [8] "The Unicode Standard, Version 2.0", The Unicode Consortium, Addison-Wesley, 1996. ISBN 0-201-48345-9. [9] "DES Modes of Operation", Federal Information Processing Standards Publication 81, National Institute of Standards and Technology, December 1980 13. Acknowledgements Thanks (in no particular order) to Jeff Haag (Jeff_Haag@3com.com), Bill Palter (palter@network-alchemy.com), Bruce Johnson (bjohnson@microsoft.com), Tony Bell (tonybe@microsoft.com), Benoit Martin (ehlija@vircom.com), and Joe Davies<EMAIL_ADDRESS>for useful suggestions and feedback. Zorn & Cobb Informational [Page 9] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 14. Chair's Address The PPP Extensions Working Group can be contacted via the current chair: Karl Fox Ascend Communications 3518 Riverside Drive Suite 101 Columbus, OH 43221 Phone: +1<PHONE_NUMBER> EMail<EMAIL_ADDRESS>15. Authors' Addresses Questions about this memo can also be directed to: Glen Zorn Microsoft Corporation One Microsoft Way Redmond, Washington 98052 Phone: +1<PHONE_NUMBER> Fax: +1<PHONE_NUMBER> EMail<EMAIL_ADDRESS>Steve Cobb Microsoft Corporation One Microsoft Way Redmond, Washington 98052 EMail<EMAIL_ADDRESS>Zorn & Cobb Informational [Page 10] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Appendix A - Pseudocode The routines mentioned in the text are described in pseudocode below. A.1 LmChallengeResponse() LmChallengeResponse( IN 8-octet Challenge, IN 0-to-14-oem-char Password, OUT 24-octet Response ) { LmPasswordHash( Password, giving PasswordHash ) ChallengeResponse( Challenge, PasswordHash, giving Response ) } A.2 LmPasswordHash() LmPasswordHash( IN 0-to-14-oem-char Password, OUT 16-octet PasswordHash ) { Set UcasePassword to the uppercased Password Zero pad UcasePassword to 14 characters DesHash( 1st 7-octets of UcasePassword, giving 1st 8-octets of PasswordHash ) DesHash( 2nd 7-octets of UcasePassword, giving 2nd 8-octets of PasswordHash ) } A.3 DesHash() DesHash( IN 7-octet Clear, OUT 8-octet Cypher ) { /* * Make Cypher an irreversibly encrypted form of Clear by * encrypting known text using Clear as the secret key. * The known text consists of the string * * KGS!@#$% */ Set StdText to "KGS!@#$%" Zorn & Cobb Informational [Page 11] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 DesEncrypt( StdText, Clear, giving Cypher ) } A.4 DesEncrypt() DesEncrypt( IN 8-octet Clear, IN 7-octet Key, OUT 8-octet Cypher ) { /* * Use the DES encryption algorithm [4] in ECB mode [9] * to encrypt Clear into Cypher such that Cypher can * only be decrypted back to Clear by providing Key. * Note that the DES algorithm takes as input a 64-bit * stream where the 8th, 16th, 24th, etc. bits are * parity bits ignored by the encrypting algorithm. * Unless you write your own DES to accept 56-bit input * without parity, you will need to insert the parity bits * yourself. */ } A.5 NtChallengeResponse() NtChallengeResponse( IN 8-octet Challenge, IN 0-to-256-unicode-char Password, OUT 24-octet Response ) { NtPasswordHash( Password, giving PasswordHash ) ChallengeResponse( Challenge, PasswordHash, giving Response ) } A.6 NtPasswordHash() NtPasswordHash( IN 0-to-256-unicode-char Password, OUT 16-octet PasswordHash ) { /* * Use the MD4 algorithm [5] to irreversibly hash Password * into PasswordHash. Only the password is hashed without * including any terminating 0. */ Zorn & Cobb Informational [Page 12] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 } A.7 ChallengeResponse() ChallengeResponse( IN 8-octet Challenge, IN 16-octet PasswordHash, OUT 24-octet Response ) { Set ZPasswordHash to PasswordHash zero-padded to 21 octets DesEncrypt( Challenge, 1st 7-octets of ZPasswordHash, giving 1st 8-octets of Response ) DesEncrypt( Challenge, 2nd 7-octets of ZPasswordHash, giving 2nd 8-octets of Response ) DesEncrypt( Challenge, 3rd 7-octets of ZPasswordHash, giving 3rd 8-octets of Response ) } A.8 LmEncryptedPasswordHash() LmEncryptedPasswordHash( IN 0-to-14-oem-char Password, IN 8-octet KeyValue, OUT 16-octet Cypher ) { LmPasswordHash( Password, giving PasswordHash ) PasswordHashEncryptedWithBlock( PasswordHash, KeyValue, giving Cypher ) } A.9 PasswordHashEncryptedWithBlock() PasswordHashEncryptedWithBlock( IN 16-octet PasswordHash, IN 8-octet Block, OUT 16-octet Cypher ) { Zorn & Cobb Informational [Page 13] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 DesEncrypt( 1st 8-octets PasswordHash, 1st 7-octets Block, giving 1st 8-octets Cypher ) DesEncrypt( 2nd 8-octets PasswordHash, 1st 7-octets Block, giving 2nd 8-octets Cypher ) } A.10 NtEncryptedPasswordHash() NtEncryptedPasswordHash( IN 0-to-14-oem-char Password IN 8-octet Challenge OUT 16-octet Cypher ) { NtPasswordHash( Password, giving PasswordHash ) PasswordHashEncryptedWithBlock( PasswordHash, Challenge, giving Cypher ) } A.11 NewPasswordEncryptedWithOldNtPasswordHash() datatype-PWBLOCK { 256-unicode-char Password 4-octets PasswordLength } NewPasswordEncryptedWithOldNtPasswordHash( IN 0-to-256-unicode-char NewPassword, IN 0-to-256-unicode-char OldPassword, OUT datatype-PWBLOCK EncryptedPwBlock ) { NtPasswordHash( OldPassword, giving PasswordHash ) EncryptPwBlockWithPasswordHash( NewPassword, PasswordHash, giving EncryptedPwBlock ) } A.12 EncryptPwBlockWithPasswordHash() EncryptPwBlockWithPasswordHash( IN 0-to-256-unicode-char Password, IN 16-octet PasswordHash, Zorn & Cobb Informational [Page 14] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 OUT datatype-PWBLOCK PwBlock ) { Fill ClearPwBlock with random octet values PwSize = lstrlenW( Password ) * sizeof( unicode-char ) PwOffset = sizeof( ClearPwBlock.Password ) - PwSize Move PwSize octets to (ClearPwBlock.Password + PwOffset ) from Password ClearPwBlock.PasswordLength = PwSize Rc4Encrypt( ClearPwBlock, sizeof( ClearPwBlock ), PasswordHash, sizeof( PasswordHash ), giving PwBlock ) } A.13 Rc4Encrypt() Rc4Encrypt( IN x-octet Clear, IN integer ClearLength, IN y-octet Key, IN integer KeyLength, OUT x-octet Cypher ) { /* * Use the RC4 encryption algorithm [6] to encrypt Clear of * length ClearLength octets into a Cypher of the same length * such that the Cypher can only be decrypted back to Clear * by providing a Key of length KeyLength octets. */ } A.14 OldNtPasswordHashEncryptedWithNewNtPasswordHash() OldNtPasswordHashEncryptedWithNewNtPasswordHash( IN 0-to-256-unicode-char NewPassword, IN 0-to-256-unicode-char OldPassword, OUT 16-octet EncryptedPasswordHash ) { NtPasswordHash( OldPassword, giving OldPasswordHash ) NtPasswordHash( NewPassword, giving NewPasswordHash ) NtPasswordHashEncryptedWithBlock( OldPasswordHash, NewPasswordHash, giving EncryptedPasswordHash ) } Zorn & Cobb Informational [Page 15] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 A.15 NewPasswordEncryptedWithOldLmPasswordHash() NewPasswordEncryptedWithOldLmPasswordHash( IN 0-to-256-unicode-char NewPassword, IN 0-to-256-unicode-char OldPassword, OUT datatype-PWBLOCK EncryptedPwBlock ) { LmPasswordHash( OldPassword, giving PasswordHash ) EncryptPwBlockWithPasswordHash( NewPassword, PasswordHash, giving EncryptedPwBlock ) } A.16 OldLmPasswordHashEncryptedWithNewNtPasswordHash() OldLmPasswordHashEncryptedWithNewNtPasswordHash( IN 0-to-256-unicode-char NewPassword, IN 0-to-256-unicode-char OldPassword, OUT 16-octet EncryptedPasswordHash ) { LmPasswordHash( OldPassword, giving OldPasswordHash ) NtPasswordHash( NewPassword, giving NewPasswordHash ) NtPasswordHashEncryptedWithBlock( OldPasswordHash, NewPasswordHash, giving EncrytptedPasswordHash ) } A.17 NtPasswordHashEncryptedWithBlock() NtPasswordHashEncryptedWithBlock( IN 16-octet PasswordHash, IN 16-octet Block, OUT 16-octet Cypher ) { DesEncrypt( 1st 8-octets PasswordHash, 1st 7-octets Block, giving 1st 8-octets Cypher ) DesEncrypt( 2nd 8-octets PasswordHash, 2nd 7-octets Block, giving 2nd 8-octets Cypher ) } Zorn & Cobb Informational [Page 16] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Appendix B - Examples B.1 Negotiation Examples Here are some examples of typical negotiations. The peer is on the left and the authenticator is on the right. The packet sequence ID is incremented on each authentication retry Response and on the change password response. All cases where the packet sequence ID is updated are noted below. Response retry is never allowed after Change Password. Change Password may occur after Response retry. The implied challenge form is shown in the examples, though all cases of "first challenge+23" should be replaced by the "C=cccccccccccccccc" challenge if authenticator supplies it in the Failure packet. B.1.1 Successful authentication <- Challenge Response -> <- Success B.1.2 Failed authentication with no retry allowed <- Challenge Response -> <- Failure (E=691 R=0) B.1.3 Successful authentication after retry <- Challenge Response -> <- Failure (E=691 R=1), disable short timeout Response (++ID) to first challenge+23 -> <- Success B.1.4 Failed hack attack with 3 attempts allowed <- Challenge Response -> <- Failure (E=691 R=1), disable short timeout Response (++ID) to first challenge+23 -> <- Failure (E=691 R=1), disable short timeout Response (++ID) to first challenge+23+23 -> Zorn & Cobb Informational [Page 17] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 <- Failure (E=691 R=0) B.1.5 Successful authentication with password change <- Challenge Response -> <- Failure (E=648 R=0 V=2), disable short timeout ChangePassword (++ID) to first challenge -> <- Success B.1.6 Successful authentication with retry and password change <- Challenge Response -> <- Failure (E=691 R=1), disable short timeout Response (++ID) to first challenge+23 -> <- Failure (E=648 R=0 V=2), disable short timeout ChangePassword (++ID) to first challenge+23 -> <- Success B.2 Hash Example Intermediate values for password "MyPw". 8-octet Challenge: 10 2D B5 DF 08 5D 30 41 0-to-256-unicode-char NtPassword: 4D 00 79 00 50 00 77 00 16-octet NtPasswordHash: FC 15 6A F7 ED CD 6C 0E DD E3 33 7D 42 7F 4E AC 24-octet NtChallengeResponse: 4E 9D 3C 8F 9C FD 38 5D 5B F4 D3 24 67 91 95 6C A4 C3 51 AB 40 9A 3D 61 B.3 Example of DES Key Generation DES uses 56-bit keys, expanded to 64 bits by the insertion of parity bits. After the parity of the key has been fixed, every eighth bit is a parity bit and the number of bits that are set (1) in each octet is odd; i.e., odd parity. Note that many DES engines do not check parity, however, simply stripping the parity bits. The following example illustrates the values resulting from the use of the 16-octet NTPasswordHash shown in Appendix B.2 to generate a pair of DES keys Zorn & Cobb Informational [Page 18] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 (e.g., for use in the NtPasswordHashEncryptedWithBlock() described in Appendix A.17). 16-octet NtPasswordHash: FC 15 6A F7 ED CD 6C 0E DD E3 33 7D 42 7F 4E AC First "raw" DES key (initial 7 octets of password hash): FC 15 6A F7 ED CD 6C First parity-corrected DES key (eight octets): FD 0B 5B 5E 7F 6E 34 D9 Second "raw" DES key (second 7 octets of password hash) 0E DD E3 33 7D 42 7F Second parity-corrected DES key (eight octets): 0E 6E 79 67 37 EA 08 FE Zorn & Cobb Informational [Page 19] RFC 2433 Microsoft PPP CHAP Extensions Ocotober 1998 Full Copyright Statement Copyright (C) The Internet Society (1998). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.  Zorn & Cobb Informational [Page 20]


If you open the sidebar and close it, you will notify content will removed before animation has been completed
This happens since OverflowControl notify all observers which has registered on hide, in this case this is the overflow directive which removes all the content. So it would be nice the overflow directive will remove content not before close animation has been done


Why string class is immutable in Java
String pool is possible only because String is immutable in Java. This way Java Runtime saves a lot of heap space because different
String variables can refer to the same String variable in the pool. If String would not have been immutable, then String interning would not have been possible
because if any variable would have changed the value, it would have been reflected in the other variables too.
If String is not immutable then it would cause a severe security threat to the application. For example, database username, password are
passed as String to get database connection and in socket programming host and port details passed as String. Since String is immutable, its value can’t be
changed otherwise any hacker could change the referenced value to cause security issues in the application.
Since String is immutable, it is safe for multithreading. A single String instance can be shared across different threads.
This avoids the use of synchronization for thread safety. Strings are implicitly thread-safe.
Strings are used in java classloader and immutability provides security that correct class is getting loaded by Classloader.
For example, think of an instance where you are trying to load java.sql.Connection class but the referenced value is changed to myhacked.
Connection class that can do unwanted things to your database. Since String is immutable, its hashcode is cached at the time of creation and it doesn’t need to be
calculated again. This makes it a great candidate for the key in a Map and its processing is faster than other HashMap key objects.
This is why String is the most widely used as HashMap keys.
Array vs ArrayList
Array: int arr[] = new int[10]
ArrayList - Implemented with the concept of dynamic array.
ArrayList: ArrayList
An array is basic functionality provided by Java. ArrayList is part of collection framework in Java.
Therefore array members are accessed using [], while ArrayList has a set of methods to access elements and modify them.
Array is a fixed size data structure while ArrayList is not. One need not to mention the size of Arraylist while creating its object.
Even if we specify some initial capacity, we can add more elements.
Array can contain both primitive data types as well as objects of a class depending on the definition of the array.
However, ArrayList only supports object entries, not the primitive data types.
Note: When we do arraylist.add(1); it converts the primitive int data type into an Integer object.
Since ArrayList cant be created for primitive data types, members of ArrayList are always references to objects at different memory locations.
Therefore in ArrayList, the actual objects are never stored at contiguous locations. References of the actual objects are stored at contiguous locations.
In array, it depends whether the arrays is of primitive type or object type. In case of primitive types, actual values are contiguous locations,
but in case of objects, allocation is similar to ArrayList.
ArrayList vs LinkedList
LinkedList - Implemented with the concept of doubly linked list.
Insertions and Removal are easy and fast in LinkedList as compared to ArrayList because there is no
risk of re sizing array and copying content to new array if array gets full which makes
adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList
in Java. ArrayList also needs to be update its index if you insert something anywhere except
at the end of array.
LinkedList has more memory overhead than ArrayList because in ArrayList each index only
holds actual object (data) but in case of LinkedList each node holds both data and address
of next and previous node.
Both LinkedList and ArrayList require O(n) time to find if an element is present or not. However we can do Binary Search on ArrayList if it is sorted and therefore can search in O(Log n) time.
Binary search on Custom Objects:
Collections.binarySearch(arrayList, 10);
Collections.binarySearch(arrayList, 50,Collections.reverseOrder());
For the best implementation of Binary search we need two prerequisites:
public static void main(String[] args)
{
// Create a list
List// Searching a domain with key value 20. To search
int index = Collections.binarySearch(l,
new Domain(20, null), c);
System.out.println("Found at index " + index);
}
1. The list must be in sorted order.
2. Any random element can be accessed in constant time.
Note: With linked list the second prerequisite is not satisfied as any random element in linked list cannot be accessed in constant time, but it must be traversed completely.
Hashmap internal working
HashMap in Java works on hashing principle. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap. Objects are stored by calling put(key, value)
method of HashMap and retrieved by calling get(key)
method.
When we call put method, hashcode()
method of the key object is called so that hash function of the map can find a bucket location to store value object, which is actually an index of the internal array, known as the table. HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object.
When we want to retrieve the object, call the get()
method and again pass the key object. This time again key object generate same hash code and we end up at same bucket location. If there is only one object then it is returned and that's our value object which you have stored earlier.
Since the internal array of HashMap is of fixed size, and if you keep storing objects, at some point of time hash function will return same bucket location for two different keys, this is called collision in HashMap. In this case, a linked list is formed at that bucket location and a new entry is stored as next node.
If we try to retrieve an object from this linked list, we need an extra check to search correct value, this is done by equals()
method. Since each node contains an entry, HashMap keeps comparing entry's key object with the passed key using equals()
and when it return true, Map returns the corresponding value.
Why HashMap not in collection framework
It is by design and Maps work with key/value pairs, while the other collections work with just values. Map maps keys to values. It allows its content to be viewed as a set of keys, a collection of values and a set of key-value mappings.
Note: "The collection framework" and “Collection interface” are not the same thing.
HashMap performance Improvement Changes in Java 8
JDK 8’s new strategy for dealing with Hash collisions. Earlier before Java 8, the performance of the HashMap was poor due to the hash collision, it degrades the performance of HashMap significantly. This change can be notifiable only when if we are using the HashMap for a large number of elements. The traversal of HashMap, get(), and other methods lookup time of HashMap have a negative impact due to hash collisions. This situation we can face when multiple keys end up in the same bucket, then values along with their keys are placed in a linked list. So, the retrieval time of elements from HashMap increases from O(1) to O(n). Because the linked list has to be traversed to get the entry in the worst case scenario. But Java 8 has come with the following new strategy for HashMap objects in case of high collisions. To address this issue, Java 8 hash elements use balanced trees instead of linked lists after a certain threshold is reached. Which means HashMap starts with storing Entry objects in a linked list but after the number of items in a hash becomes larger than a certain threshold. The hash will change from using a linked list to a balanced tree. Above changes ensure the performance of O(log(n)) in worst case scenarios and O(1) with proper hashCode(). The alternative String hash function added in Java 7 has been removed.
Sort Hashmap by value and key
// by value
public static HashMap sortByValue(HashMap hm) {
// Create a list from elements of HashMap
List > list = new LinkedList >(hm.entrySet());
// Sort the list
Collections.sort(list, new Comparator>() {
@Override
public int compare(Map.Entry o1, Map.Entry o2) {
return (o1.getValue()).compareTo(o2.getValue());
}
});
// put data from sorted list to hashmap
HashMap temp = new LinkedHashMap();
for (Map.Entry aa : list) {
temp.put(aa.getKey(), aa.getValue());
}
return hm;
}
// by key
TreeMap sorted = new TreeMap<>(map);
// OR
TreeMap sorted = new TreeMap<>();
// Copy all data from hashMap into TreeMap
sorted.putAll(map);
// Display the TreeMap which is naturally sorted
for (Map.Entry entry : sorted.entrySet())
System.out.println("Key = " + entry.getKey() +", Value = " + entry.getValue());
Check two Hashmaps are equal
map1.equals(map2); //check key and values as equals
map1.keySet().equals(map2.keySet()); //Check only key sets
new ArrayList<>(map1.values()).equals(new ArrayList<>(map2.values())); //Check only values
new HashSet<>(map1.values()).equals(new HashSet<>(map2.values())); //allowed duplicates here
Please note that in case of custom classes as key or value we need to override the equals and hashcode method.
Check two objects are same in Hashset. Override Equals and Hashcode methods.
Override Equals and Hashcode method of the custom class using the fields.
Object a = new Object ("pankaj","1");
Object b = new Object ("pankaj","1");
Now only one object will be stored in Hashset because hashcode and equals methods are overriden as shown below.
//hashCode
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
//equals
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SetCustomClass other = (SetCustomClass) obj;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
Fail-fast vs Fail-safe : ConcurrentModificationException
fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun. Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection. fail-fast behavior is implemented by keeping a modification count and if iteration thread realizes the change in modification count it throws ConcurrentModificationException.
fail-safe iterator doesn't throw any Exception if Collection is modified structurally while one thread is Iterating over it because they work on clone of Collection instead of original collection and that’s why they are called as fail-safe iterator. Iterator of CopyOnWriteArrayList is an example of fail-safe Iterator also iterator written by ConcurrentHashMap keySet is also fail-safe iterator and never throw ConcurrentModificationException in Java.
To Avoid ConcurrentModificationException in single-threaded environment
Use the iterator remove() function to remove the object from underlying collection object. But in this case, you can remove the same object and not any other object from the list.
To Avoid ConcurrentModificationException in multi-threaded environment
Convert the list to an array and then iterate on the array. This approach works well for small or medium size list but if the list is large then it will affect the performance a lot.
Lock the list while iterating by putting it in a synchronized block. This approach is not recommended because it will cease the benefits of multithreading.
Use ConcurrentHashMap and CopyOnWriteArrayList classes. This is the recommended approach to avoid concurrent modification exception.
HashMap vs LinkedHashMap vs TreeMap vs Hashtable
HashMap: HashMap offers 0(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
A HashMap contains values based on the key.It contains only unique elements.
It may have one null key and multiple null values.
It maintains no order.
LinkedHashMap: LinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.
public class LinkedHashMap extends HashMap implements Map
A LinkedHashMap contains values based on the key.It contains only unique elements.
It may have one null key and multiple null values.
It is same as HashMap instead maintains insertion order.
TreeMap: TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface. TreeMap is implemented by a Red-Black Tree.
public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, Serializable
A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.It contains only unique elements.
It cannot have null key but can have multiple null values.
It is same as HashMap instead maintains ascending order(Sorted using the natural order of its key).
Hashtable: “Hashtable” is the generic name for hash-based maps.
public class Hashtable extends Dictionary implementsMap, Cloneable, Serializable
A Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.It contains only unique elements.
It may have not have any null key or value.
It is synchronized.
It is a legacy class.
HashMap vs HashTable vs SynchronisedMap vs ConcurrentHashMap
Comparable vs Comparator
Chained Comparator: Sort a List by multiple attributes
Suppose we have a class Employee having three variables JobTitle, age and salary and we need to sort using all three variables.
Use Chained Comparator- Create three sorting sequence class for Employee using Comparator interface.
And then pass to chained Comparator as shown below.
public class EmployeeChainedComparator implements Comparator {
private List> listComparators;
@SafeVarargs
public EmployeeChainedComparator(Comparator... comparators) {
this.listComparators = Arrays.asList(comparators);
}
@Override
public int compare(Employee emp1, Employee emp2) {
for (Comparator comparator : listComparators) {
int result = comparator.compare(emp1, emp2);
if (result != 0) {
return result;
}
}
return 0;
}
}
//Job title comparator:
public class EmployeeJobTitleComparator implements Comparator {
@Override
public int compare(Employee emp1, Employee emp2) {
return emp1.getJobTitle().compareTo(emp2.getJobTitle());
}
}
//Age comparator:
public class EmployeeAgeComparator implements Comparator {
@Override
public int compare(Employee emp1, Employee emp2) {
return emp1.getAge() - emp2.getAge();
}
}
//Salary comparator:
public class EmployeeSalaryComparator implements Comparator {
@Override
public int compare(Employee emp1, Employee emp2) {
return emp1.getSalary() - emp2.getSalary();
}
}
//Main: Pass all three comparator to Chained comparator to sort using all variables.
Collections.sort(listEmployees, new EmployeeChainedComparator(
new EmployeeJobTitleComparator(),
new EmployeeAgeComparator(),
new EmployeeSalaryComparator())
);
Final Reference to an Object
In final reference we cannot change the reference but we can change the object values. That is the main difference between final reference and immutable class.
Final means that you can't change the object's reference to point to another reference or another object, but you can still mutate its state (using setter methods)
Where immutable means that the object's actual value can't be changed, but you can change its reference to another one.
OutOfMemoryError vs StackOverflowError
OutOfMemoryError is related to Heap.
StackOverflowError is related to stack.
When you start JVM you define how much RAM it can use for processing. JVM divides this into certain memory locations for its processing purpose, two of those are Stack & Heap
If you have large objects (or) referenced objects in memory, then you will see OutofMemoryError. If you have strong references to objects, then GC can't clean the memory space allocated for that object. When JVM tries to allocate memory for new object and not enough space available it throws OutofMemoryError because it can't allocate the required amount of memory.
How to avoid: Make sure un-necessary objects are available for GC.
All your local variables and methods calls related data will be on the stack. For every method call, one stack frame will be created and local as well as method call related data will be placed inside the stack frame. Once method execution is completed, the stack frame will be removed. ONE WAY to reproduce this is, have an infinite loop for method call, you will see StackOverflowError, because stack frame will be populated with method data for every call but it won't be freed (removed).
How to avoid: Make sure method calls are ending (not in an infinite loop)
ClassNotFoundException Vs NoClassDefFoundError
Java.lang.ThreadLocal class in Java
The Java ThreadLocal class enables you to create variables that can only be read and written by the same thread. Thus, even if two threads are executing the same code, and the code has a reference to the same ThreadLocal variable, the two threads cannot see each other's ThreadLocal variables. Thus, the Java ThreadLocal class provides a simple way to make code thread safe that would not otherwise be so.
private ThreadLocal threadLocal = new ThreadLocal();
threadLocal.set("A thread local value");
String threadLocalValue = (String) threadLocal.get();
threadLocal.remove();
Why wait in object class (Object has monitors)
Multiple threads can access one Object. Only one thread can hold object monitor at a time for synchronized methods/blocks.
wait(), notify(), notifyAll()
method being in Object class allows all the threads created on that object to communicate with other.
Locking ( using synchronized or Lock API) and Communication (wait() and notify()) are two different concepts.
If Thread class contains wait(), notify(), notifyAll()
methods, then it will create below problems:
Thread communication problem
Synchronization on object won’t be possible. If each thread will have monitor, we won’t have any way of achieving synchronization
Inconsistency in state of object.
If wait() and notify() were on the Thread instead then each thread would have to know the status of every other thread. How would thread1 know that thread2 was waiting for access to a particular resource? If thread1 needed to call thread2.notify()
it would have to somehow find out that thread2 was waiting. There would need to be some mechanism for threads to register the resources or actions that they need so others could signal them when stuff was ready or available.
yield vs Join vs sleep
yield()
method pauses the currently executing thread temporarily for giving a chance to the remaining waiting threads of the same priority to execute. If there is no waiting thread or all the waiting threads have a lower priority then the same thread will continue its execution. The yielded thread when it will get the chance for execution is decided by the thread scheduler whose behavior is vendor dependent.
join()
If any executing thread t1 calls join() on t2 i.e; t2.join() immediately t1 will enter into waiting state until t2 completes its execution.
sleep()
Based on our requirement we can make a thread to be in sleeping state for a specified period of time (hope not much explanation required for our favorite method).
Singleton design pattern
We need to have static member of class, private constructor and static factory method.
Static member: It gets memory only once because of static, it contains the instance of the Singleton class.
Private constructor: It will prevent to instantiate the Singleton class from outside the class.
Static factory method: This provides the global point of access to the Singleton object and returns the instance to the caller.
class Singleton{
private static Singleton obj;
private Singleton(){}
public static Singleton getA(){
if (obj == null){
synchronized(Singleton.class){
if (obj == null){
//instance will be created at request time
obj = new Singleton();
}
}
}
return obj;
}
}
Immutable class
There are many immutable classes like String, Boolean, Byte, Short, Integer, Long, Float, Double etc. In short, all the wrapper classes and String class is immutable. We can also create immutable class by creating final class that have final data members as the example given below:
public final class Employee{
final String pancardNumber;
public Employee(String pancardNumber){
this.pancardNumber=pancardNumber;
}
public String getPancardNumber(){
return pancardNumber;
}
}
To create a custom immutable class we have to do the following stepsDeclare the class as final so it can’t be extended. If class is not final, one can extend this class and change the behavior using super in the constructor.
Make all fields private so that direct access is not allowed.
Do not provide setter methods (methods that modify fields) for variables, so that it can not be set.
Make all mutable fields final so that their values can be assigned only once.
Initialize all the fields through a constructor doing the deep copy.
Perform cloning of objects in the getter methods to return a copy rather than returning the actual object reference.
If the instance fields include references to mutable objects, don’t allow those objects to be changed
Don’t provide methods that modify the mutable objects.
Don’t share references to the mutable objects. Never store references to external, mutable objects passed to the constructor. If necessary, create copies and store references to the copies. Similarly, create copies of our internal mutable objects when necessary to avoid returning the originals in our methods.
Deep and Shallow copy
Shallow copy of an object copies the ‘main’ object, but doesn’t copy the inner objects. The ‘inner objects’ are shared between the original object and its copy. For example, in our Person object, we would create a second Person, but both objects would share the same Name and Address objects.
The problem with the shallow copy is that the two objects are not independent. If you modify the Name object of one Person, the change will be reflected in the other Person object.
Say we have a Person object with a reference variable mother; then, we make a copy of mother, creating a second Person object, son. If later on in the code, the son tries to moveOut()
by modifying his Address object, the mother moves with him! This occurs because our mother and son objects share the same Address object.
public class Person {
private Name name;
private Address address;
public Person(Person originalPerson) {
this.name = originalPerson.name;
this.address = originalPerson.address;
}
[…]
}
//main
Person mother = new Person(new Name(…), new Address(…));
[…]
Person son = new Person(mother);
[…]
son.moveOut(new Street(…), new City(…));
Deep Copy unlike the shallow copy, a deep copy is a fully independent copy of an object. If we copied our Person object, we would copy the entire object structure.A change in the Address object of one Person wouldn’t be reflected in the other object. If we take a look at the code in example , you can see that we’re not only using a copy constructor on our Person object, but we are also utilizing copy constructors on the inner objects as well.
Using this deep copy, we can retry the mother-son example. Now the son is able to successfully move out!.
However, that’s not the end of the story. To create a true deep copy, we need to keep copying all of the Person object’s nested elements, until there are only primitive types and “Immutables” left. Let’s look at the Street class to better illustrate this:
public class Person {
private Name name;
private Address address;
public Person(Person otherPerson) {
this.name = new Name(otherPerson.name);
this.address = new Address(otherPerson.address);
}
[…]
}
//keep copying all of the Person object’s nested elements,
//until there are only primitive types and “Immutables” left
public class Street {
private String name;
private int number;
public Street(Street otherStreet){
this.name = otherStreet.name;
this.number = otherStreet.number;
}
[…]
}
Serializable and Externalizable
The Java's java.io.Serializable
is a marker interface, means that it contains no methods or fields and serves only to identify the semantics of being serializable. Therefore, a class implementing Serializable does not have to implement any specific methods . It is just used to "mark" java classes that their state can be serialized or deserialized.
If you try to serialize an object of a class which implements serializable, but the object includes a reference to an non-serializable class then a NotSerializableException will be thrown at runtime.
The serialization runtime associates with each serializable class a version number, called a serialVersionUID, which is used during deserialization to verify that the sender and receiver of a serialized object have loaded classes for that object that are compatible with respect to serialization. If the receiver has loaded a class for the object that has a different serialVersionUID than that of the corresponding sender's class, then deserialization will result in an InvalidClassException. A serializable class can declare its own serialVersionUID explicitly by declaring a field named serialVersionUID that must be static, final, and of type long:
ANY-ACCESS-MODIFIER static final long serialVersionUID = 42L;
If a serializable class does not explicitly declare a serialVersionUID, then the serialization runtime will calculate a default serialVersionUID value for that class based on various aspects of the class, as described in the Java(TM) Object Serialization Specification.
Externalizable provides us writeExternal()
and readExternal()
method which gives us flexibility to control java serialization mechanism instead of relying on Java's default serialization. Correct implementation of Externalizable interface can improve performance of application drastically.
// Serialization
try{
//Saving of object in a file
FileOutputStream file = new FileOutputStream(filename);
ObjectOutputStream out = new ObjectOutputStream(file);
// Method for serialization of object
out.writeObject(object);
out.close();
file.close();
System.out.println("Object has been serialized");
}
// Deserialization
try{
// Reading the object from a file
FileInputStream file = new FileInputStream(filename);
ObjectInputStream in = new ObjectInputStream(file);
// Method for deserialization of object
object1 = (Demo)in.readObject();
in.close();
file.close();
System.out.println("Object has been deserialized ");
}
Shuffle ArrayList
Collections.shuffle() is used to shuffle lists in java.
Collections.shuffle(mylist);
// Here we use Random() to shuffle given list.
Collections.shuffle(mylist, new Random());
// Here we use Random(3) to shuffle given list. Here 3
// is seed value for Random.
Collections.shuffle(mylist, new Random(3));
Function to generate a random permutation of arr[].static void randomize( int arr[], int n)
{
Random r = new Random();
// Start from the last element and swap one by one.
for (int i = n-1; i > 0; i--){
// Pick a random index from 0 to i
int j = r.nextInt(i);
// Swap arr[i] with the element at random index
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// main method
public static void main(String[] args)
{
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int n = arr.length;
randomize (arr, n);
}
Reverse a String
Reverse String using toCharArray().
public static void main(String[] args) {
String s = "sachin";
for (int i =s.length()-1; i>=0;i--) {
s=s + s.toCharArray()[i];
}
}
Using Recurrsion.
public static String reverse(String str) {
if ((str==null)||(str.length() <= 1)) {
return str;
}
else
{
return str.substring(str.length()-1) + reverse(str.substring(0,str.length()-1));
}
}
S.O.L.I.D Principles
S.O.L.I.D represents five principles of Java which are:
S: Single responsibility principle
O: Open-closed principle
L: Liskov substitution principle
I: Interface segregation principle
D: Dependency inversion principle
According to the single responsibility principle, there should be only one reason due to which a class has to be changed. It means that a class should have one task to do.
The principle can be well understood with an example. Imagine there is a class which performs following operations.
connected to a database.
read some data from database tables.
finally, write it to a file.
Have you imagined the scenario? Here the class has multiple reasons to change, and few of them are the modification of file output, new data base adoption. When we are talking about single principle responsibility, we would say, there are too many reasons for the class to change; hence, it doesn’t fit properly in the single responsibility principle.
According to open closed principle, entities or objects should remain open for extension, but they should stay closed for modification. To be precise, according to this principle, a class should be written in such a manner that it performs its job flawlessly without the assumption that people in the future will simply come and change it. Hence, the class should remain closed for modification, but it should have the option to get extended. Ways of extending the class include:
Inheriting from the class.
Overwriting the required behaviors from the class.
Extending certain behaviors of the class.
Liskov substitution principle the only thing is that every subclass or derived class should be substitutable for their parent or base class.
You can say that it is a unique object-oriented principle. The principle can further be simplified by understanding this principle; a child type of a particular parent type without making any complication or blowing things up should have the ability to stand in for that parent. This principle is closely related to Liskov Substitution principle.
According to interface segregation principle, a client, no matter what should never be forced to implement an interface that it does not use or the client should never be obliged to depend on any method, which is not used by them.
So basically, the interface segregation principles as you prefer the interfaces, which are small but client specific instead of monolithic and bigger interface.
According to dependency inversion principle, entities should depend only on abstractions but not on concretions. According to it, the high-level module must never rely on any low-level module but should depend on abstractions.


{% trans 'Do you think we can help you with advice in the cannabis industry?' %}
{% trans 'Do you have questions about the use of the platform?' %}
---
{% trans 'Feel free to contact us, we will be happy to talk about how we can help boost the cannabis industry and to listen your doubts and suggestions.' %}


View the open-source code. Text adapted from Trinity Student Handbook, with MLA citation style
Original source: The American, probably more than any other man, is prone to be apologetic about the trade he follows. He seldom believes that it is quite worthy of his virtues and talents; almost always he thinks that he would have adorned something far gaudier. Unfortunately, it is not always possible for him to escape, or even for him to dream plausibly of escaping, so he soothes himself by assuring himself that he belongs to a superior section of his craft, and very often he invents a sonorous name to set himself off from the herd. Here we glimpse the origin of a multitude of characteristic American euphemisms, e.g., mortician for undertaker, realtor for real-estate agent, electragist for electrical contractor ... so on (Mencken 284).
Author 1: As Mencken says, “The American, probably more than any other
man, is prone to be apologetic about the trade he follows" (284).
HINT
Author 2: As Mencken says, the American believes that he would have adorned something gaudier, so he soothes himself by inventing a sonorous name to set himself off from the herd (284).
HINT
Author 3: Mencken explains the origin of these professional euphemisms as lying in the American’s vanity; the American feels that he is really better than his profession, but since he cannot escape it, he tries to make it at least sound worthy of him (284).
HINT


“From Compulsion to Choice”
Search within yourself by Chade-Meng Tan, Chapter 5: Riding your emotions like a horse
When programming, what are some of your triggers? What causes a disproportionate emotional response?
Like I said in my previous blogs I did alot work on myself a couple of years back and I found my two big triggers are not being heard and wasting time. My brain buzzes at 2000 miles an hour sometimes and I can switch topics faster than I can verbalise, so not being given the space to make my point frustrates and angers me. The other is wasting time, I like my feedback and directions direct and straight to the point so I can process the thing and just get onto it. I can be very blunt unintentionally when someone doesn’t get to the point or let em ask the direct questions to get to the point. I’m not a fan of mindless babble and like to get my info and then move on.
How did you find the Siberian North Railroad exercise (Stop, Breathe, Notice, Reflect, Respond)?
I work a high stress and sometime mentally draining job. You get confronted on a day n day out unadulterated emotions from rage to joy. The calls that get me are when people don’t get the answers they want to hear and they blame you. Its frustrates me because it's honestly and completely not my fault as I am just the messenger and being made to feel that helpless and in many cases powerless which sets of the “Not being heard or understood” trigger. I used this method this week on the phone and used the mute and volume down buttons liberally.  It also help me get perspective on what I am dealing with at the core and helped me remove the emotional impact as well. I became more of nicer person to be around as well, so bonus!


Penguinn JS
Single sequence
Multiple sequences (FASTA)
Multiple sequences (line separated)
Predict
For more info about Penguinn, see
https://github.com/ML-Bioinfo-CEITEC/penguinn
.


PDS Git and Github Guide¶
-
[@mentions Email Filter](#mentions-email-filter)
Getting Started with Github¶
Instead of reinventing the wheel, there are countless trainings online. Here are few good ones we have found: * Lynda.com: https://www.lynda.com/Git-training-tutorials/1383-0.html * TBD
Notifications¶
To ensure you are up-to-date with all things happening in repositories, check your notification settings send you emails / mobile notifications when needed. For PDS development, at minimum, please check the following: * Participating: :white_check_mark: Email, :white_check_mark: Web and Mobile * Watching: :white_check_mark: Email, :white_check_mark: Web and Mobile
@mentions Email Filter¶
Think of a Github @mention as a direct message, versus other issue and commit notifications being group messages. It is highly recommended you setup an email filter to pull out these @mentions (aka direct messages) so you are able to respond in a timely manner.
Here is an example email filter from Microsoft Outlook for Mac:
When a new message arrives that meets all these conditions:
Body Contains @my_username
Subject Contains "NASA-PDS/" or "NASA-PDS/" or "pds-data-dictionaries/"
Do the following:
Move to Folder PDS-@mentions (you may need to create this folder somewhere)
[checked] Do not apply other rules to message that meet the same conditions
[checked] Enabled
Commit Message Best Practices¶
For commit message best practices, the PDS tries to follow these Github Commit Messages Guidelines where possible.
Once you have read through the guidelines, here are some highlights to touch on and some additional notes:
A properly formed git commit subject line should always be able to complete the following sentence
If applied, this commit will <your subject line here>
Rules for a great commit message style
Separate subject from body with a blank line
Do not end the subject line with a period
Capitalize the subject line and each paragraph
Use the imperative mood in the subject line
Wrap lines at 72 characters
Use the body to explain what and why you have done something. In most cases, you can leave out details about how a change has been made.
References in commit messages
If the commit refers to an issue, add this information to the commit message header or body.
See how to autolink references and urls for more information on linking to other issues, repos, commits, etc.
Do this for ticket references, people, etc.
Be sure use the correct referencing method when going across repositories.
Short (72 chars or less) summary
More detailed explanatory text. Wrap it to 72 characters. The blank
line separating the summary from the body is critical (unless you omit
the body entirely).
Write your commit message in the imperative: "Fix bug" and not "Fixed
bug" or "Fixes bug." This convention matches up with commit messages
generated by commands like git merge and git revert.
Further paragraphs come after blank lines.
- Bullet points are okay, too.
- Typically a hyphen or asterisk is used for the bullet, followed by a
single space. Use a hanging indent.
For example:
$ git add my_file.txt
# Try to avoid using `git commit -m` unless it is a very trivial update/change
$ git commit
# Vim or Emacs window will open. To change editor that opens, see https://help.github.com/en/github/using-git/associating-text-editors-with-git .
Created new my_file with text in it
This new file includes:
* Part 1
* Part 2
* Part 3
Issue Tracking¶
See more information at PDS Issue Tracking Guide
Advanced Help¶
Help With Rebasing¶
Rebasing can get messy and be painful. We highly recommend reading this article on The Golden Rule of Rebasing.


PING-PONG
HOME
INSTRUCTIONS
ABOUT
Ping Pong will count up to your number from number 1
ENTER A NUMBER
PLAY


Algorithms for Walking, Running, Swimming, Flying, and Manipulation
© Russ Tedrake, 2023
Last modified .
How to cite these notes, use annotations, and give feedback.
Note: These are working notes used for a course being taught at MIT. They will be updated throughout the Spring 2023 semester. Lecture videos are available on YouTube.
| Previous Chapter | Table of contents | Next Chapter |
The discussion of walking and running robots in Chapter 4 motivated the notion of limit cycle stability. Linear systems are not capable of producing stable limit cycle behavior, so this rich topic is unique to nonlinear systems design and analysis. Furthermore, the tools that are required to design, stabilize, and verify limit cycles will have applicability beyond simple periodic motions.
The first natural question we must ask is, given a system $\dot{\bx} = f(\bx)$, or a control system $\dot{x} = f(\bx,\bu)$, how do we go about finding periodic solutions which may be passively stable, open-loop stable, or stabilizable via closed-loop feedback? It turns out that the trajectory optimization tools that we developed already are very well suited to this task.
I introduced the trajectory optimization tools as means for optimizing a control trajectory starting from a particular known initial condition. But the fundamental idea of optimizing over individual trajectories of the system is useful more broadly. Even for a passive system, we can formulate the search for a periodic solution as an optimization over trajectories that satisfy the dynamic constraints and periodicity constraints, $\bx[0] = \bx[N]$: \begin{align*} \find_{\bx[\cdot]} \quad \subjto \quad & \bx[n+1] = f(\bx[n]), \quad \forall n\in[0, N-1] \\ & \bx[0] = \bx[N]. \end{align*} Certainly we can add control inputs back into the formulation, too, but let's start with this simple case. Take a moment to think about the feasible solutions to this problem formulation. Certainly a fixed point $\bx[n] = \bx^*$ will satisfy the constraints; if we don't want these solutions to come out of the solver we might need to exclude them with constraints or add an objective that guides the solver towards the desired solutions. The other possible solutions are trajectories that are periodic in exactly $N$ steps. That's pretty restrictive.
We can do better if we use the continuous-time formulations. For instance, in our introduction of direct collocation, we wrote \begin{align*} \min_{\bx[\cdot],\bu[\cdot]} \quad & \ell_f(\bx[N]) + \sum_{n_0}^{N-1} h_n \ell(\bx[n],\bu[n]) \\ \subjto \quad & \dot\bx(t_{c,n}) = f(\bx(t_{c,n}), \bu(t_{c,n})), & \forall n \in [0,N-1] \\ & \bx[0] = \bx_0 \\ & + \text{additional constraints}. \end{align*} But we can also add $h_n$ as decision variables in the optimization (reminder: I recommend setting a lower-bound $h_n \ge h_{min} > 0$). This allows our $N$-step trajectory optimization to scale and shrink time in order to satisfy the periodicity constraint. The result is simple and powerful.
Recall the dynamics of the Van der Pol oscillator given by $$\ddot{q} + \mu (q^2 - 1) \dot{q} + q = 0, \quad \mu>0,$$ which exhibited a stable limit cycle.
Formulate the direct collocation optimization: \begin{align*} \find_{\bx[\cdot],h} \quad \subjto \quad & q[0] = 0, \quad \dot{q}[0] > 0, \\ & \bx[N] = \bx[0], \text{(periodicity constraint)}\\ & \text{collocation dynamic constraints} \\ & 0.01 \le h \le 0.5 \end{align*}
Try it yourself:
As always, make sure that you take a look at the code. Poke around. Try changing some things.
One of the things that you should notice in the code is that I provide an initial guess for the solver. In most of the examples so far I've been able to avoid doing that--the solver takes small random numbers as a default initial guess and solves from there. But for this problem, I found that it was getting stuck in a local minima. Adding the initial guess that the solution moves around a circle in state space was enough.
Recall the important distinction between stability of a trajectory in time and stability of a limit cycle was that the limit cycle does not converge in phase -- trajectories near the cycle converge to the cycle, but trajectories on the cycle may not converge with each other. This is type of stability, also known as orbital stability can be written as stability to the manifold described by a trajectory $\bx^*(t)$, \[ \min_\tau || x(t) - x^*(\tau) || \rightarrow 0.\] In the case of limit cycles, this manifold is a periodic solution with $\bx^*(t+t_{period}) = \bx^*(t)$. Depending on exactly how that convergence happens, we can define orbital stability in the sense of Lyapunov, asymptotic orbital stability, exponential orbital stability, or even finite-time orbital stability.
In order to prove that a system is orbitally stable (locally, over a region, or globally), or to analyze the region of attraction of a limit cycle, we can use a Lyapunov function. When we analyzed our simple models of walking and running, we carried out the analysis on the Poincare map. Indeed, if we can find a Lyapunov function that proves (i.s.L., asympototic, or exponential) stability of the discrete Poincare map, then this implies (i.s.L, asymptotic, or exponential) orbital stability of the cycle. But Lyapunov functions of this form are difficult to verify for a pretty fundamental reason: we rarely have an analytical expression for the Poincare map, since it is the result of integrating a nonlinear dynamics over the cycle.
Instead, we will focus our attention on constructing Lyapunov functions in the full state space, which use the continuous dynamics. In particular, we would like to consider Lyapunov functions which have the form cartooned below; they vanish to zero everywhere along the cycle, and are strictly positive everywhere away from the cycle.
How can we parameterize this class of functions? For arbitrary cycles this could be very difficult in the original coordinates. For simple cycles like in the cartoon, one could imagine using polar coordinates. More generally, we will define a new coordinate system relative to the orbit, with coordinates
Given a state $\bx$ in the original coordinates, we must define a smooth mapping $\bx \rightarrow (\tau, \bx_\perp)$ to this new coordinate system. For example, for a simple ring oscillator we might have:
In general, for an $n$-dimensional state space, $\tau$ will always be a scalar, and $\bx_\perp$ will be an $(n-1)$-dimensional vector defining the remaining coordinates relative to $\bx^*(\tau)$. In fact, although we use the notation $\bx_\perp$ the coordinate system need not be strictly orthogonal to the orbit, but must simply be transversal (not parallel). Having defined the smooth mapping $\bx \rightarrow (\tau,\bx_\perp)$, we can always rewrite the dynamics in this new coordinate system: \begin{gather*} \dot{\tau} = f_\tau(\bx_\perp,\tau) \\ \dot\bx_\perp = f_\perp(\bx_\perp,\tau). \end{gather*} To keep our notation simpler for the remainder of these notes, we will assume that the origin of this new coordinate system is on the nominal trajectory ($\min_\tau |\bx - \bx^*(\tau)| = 0 \Rightarrow \bx_\perp = 0$). Similarly, by taking $\tau$ to be the phase variable, we will leverage the fact that on the nominal trajectory, we have $\dot\tau = f_\tau(0, \tau) = 1.$The value of
this construction for Lyapunov analysis was proposed in
For a dynamical system $\dot\bx = f(\bx)$ with $\bx \in \Re^n$, $f$ continuous, a continuous periodic solution $\bx^*(\tau)$, and a smooth mapping $\bx \rightarrow (\tau,\bx_\perp)$ where $\bx_\perp$ vanishes on $\bx^*$, then for some $n-1$ dimensional ball ${\cal B}$ around the origin, if I can produce a $V(\bx_\perp,\tau)$ such that \begin{gather*} \forall \tau, V(0,\tau) = 0, \\ \forall \tau, \forall \bx_\perp \in {\cal B}, \bx_\perp \ne 0, V(\bx_\perp,\tau) > 0, \end{gather*} with \begin{gather*} \forall \tau, \dot{V}(0,\tau) = 0, \\ \forall \tau, \forall \bx_\perp \in {\cal B}, \bx_\perp \ne 0, \dot{V}(\bx_\perp,\tau) < 0, \end{gather*} then the solution $\bx^*(t)$ is locally orbitally asymptotically stable.
Orbital stability in the sense of Lyapunov and exponential orbital stability can also be verified (with $\dot{V}_\perp \le 0$ and $\dot{V}_\perp \le \alpha V_\perp$, respectively).
Perhaps the simplest oscillator is the first-order system which converges to the unit circle. In cartesian coordinates, the dynamics are \begin{align*} \dot{x}_1 =& x_2 -\alpha x_1 \left( 1 - \frac{1}{\sqrt{x_1^2+x_2^2}}\right) \\ \dot{x}_2 =& -x_1 -\alpha x_2 \left( 1 - \frac{1}{\sqrt{x_1^2+x_2^2}}\right), \end{align*} where $\alpha$ is a positive scalar gain.
If we take the transverse coordinates to be the polar coordinates, shifted so that $x_\perp$ is zero on the unit circle, \begin{align*}\tau =& \text{atan2}(-x_2,x_1) \\ x_\perp =& \sqrt{x_1^2+x_2^2}-1, \end{align*} which is valid when $x_\perp>-1$, then the simple transverse dynamics are revealed: \begin{align*} \dot\tau =& 1 \\ \dot{x}_\perp =& -\alpha x_\perp. \end{align*} Taking a Lyapunov candidate $V(x_\perp,\tau) = x_\perp^2$, we can verify that $$\dot{V} = -2 \alpha x_\perp^2 < 0, \quad \forall x_\perp > -1.$$ This demonstrates that the limit cycle is locally asymptotically stable, and furthermore that the invariant open-set $V < 1$ is inside the region of attraction of that limit cycle. In fact, we know that all $x_\perp > -1$ are in the region of attraction that limit cycle, but this is not proven by the Lyapunov argument above.
Let's compare this approach again with the approach that we used in the chapter on walking robots, where we used a Poincaré map analysis to investigate limit cycle stability. In transverse coordinates approach, there is an additional burden to construct the coordinate system along the entire trajectory, instead of only at a single surface of section. In fact, the transverse coordinates approach is sometimes referred to as a "moving Poincaré section". Again, the reward for this extra work is that we can check a condition that only involves the instantaneous dynamics, $f(\bx)$, as opposed to having to integrate the dynamics over an entire cycle to generate the discrete Poincaré map, $\bx_p[n+1] = P(\bx_p[n])$. As we will see below, this approach will also be more compatible with designing continuous feedback controller that stabilize the limit cycle.
In the case of Lyapunov analysis around a fixed point, there was an important special case: for stable linear systems, we actually have a recipe for constructing a Lyapunov function. As a result, for nonlinear systems, we often found it convenient to begin our search by linearizing around the fixed point and using the Lyapunov candidate for the linear system as an initial guess. That same approach can be extended to limit cycle analysis.
In particular, let us make a linear approximation of the transverse
dynamics: $$\dot{\bx}_\perp = f_\perp(\bx_\perp, \tau) \approx
\pd{f_\perp}{\bx_\perp} \bx_\perp = \bA_\perp(\tau)\bx_\perp.$$ Note that
I've assumed that $\bx_\perp$ is zero on the nominal trajectory, so don't
need the additional notation of working in the error coordinates here.
Remember that $\tau$ is the phase along the trajectory, but
This is very powerful. It gives us a general way to construct a Lyapunov candidate that certifies local stability of the cycle, and which can be used as a candidate for nonlinear Lyapunov analysis.
Coming soon. If you are interested, see
Many of the tools we've developed for stabilization of fixed points or stabilization of trajectories can be adapted to this new setting. When we discussed control for the spring-loaded inverted pendulum model, we considered discrete control decisions, made once per cycle, which could stabilize the discrete Poincare map, $\bx_p[n+1] = f_p(\bx_p[n], \bu[n]),$ with $\bu[n]$ the once-per-cycle decisions. While it's possible to get the local linear approximations of this map using our adjoint methods, remember that we rarely have an analytical expression for the nonlinear $f_p$.
How limiting is it to restrict ourselves to once-per-cycle decisions? Of course we can improve performance in general with continuous feedback. But there are also some cases where once-per-cycle decisions feel quite reasonable. Foot placement for legged robots is a good example -- once we've chosen a foot placement we might make minor corrections just before we place the foot, but rarely change that decision once the foot is on the ground; once per footstep seems like a reasonable approximation. Another good example is flapping flight: here the wing beat cycle times can be much faster than the dynamic timescales of the center of mass, and changing the parameters of the wing stroke one per flap seems pretty reasonable.
But the tools we've developed above also give us the machinery we need to consider continuous feedback throughout the trajectory. Let's look at a few important formulations.
It turns out many of our simple walking models -- particularly ones with a point foot that are derived in the minimal coordinates -- are only short one actuator (between the foot and the ground). One can represent even fairly complex robots this way; much of the theory that I'll elude to here was originally developed by Jessy Grizzle and his group in the context of the bipedal robot RABBIT. Jessy's key observation was that limit cycle stability is effectively stability in $n-1$ degrees of freedom, and you can often achieve it easily with $n-1$ actuators -- he called this line of work "Hybrid Zero Dynamics" (HZD). We'll deal with the "hybrid" part of that in the next chapter, but here is a simple example to illustrate the "zero dynamics" concept. [Coming soon...]
Stabilizing the zero dynamics is synonymous with achieving orbital stability. Interestingly, it doesn't actually guarantee that you will go around the limit cycle. One "feature" of the HZD walkers is that you can actually stand in front of them and stop their forward progress with your hand -- the control system will continue to act, maintaining itself on the cycle, but progress along the cycle has stopped. In some of the robots you could even push them backwards and they would move through the same walking cycle in reverse. If one wants to certify that forward progress will be achieved, then the tasks is reduced to inspecting the one-dimensional dynamics of the phase variable along the cycle.
The notion of "zero dynamics" is certainly not restricted to systems with underactuation of degree one. In general, we can easily stabilize a manifold of dimension $m$ with $m$ actuators (we saw this in the section on task-space partial feedback linearization), and if being on that manifold is sufficient to achieve our task, or if we can certify that the resulting dynamics on the manifold are sufficient for our task, then life is good. But in the "underactuation degree one" case, the manifold under study is a trajectory/orbit, and the tools from this chapter are immediately applicable.
Another natural approach to stabilizing a cycle uses the transverse
linearization. In particular, for a nominal (control) trajectory,
$[\bx_0(t), \bu_0(t)],$ with $\dot{\bx}_0 = f(\bx_0, \bu_0)$, we can
approximate the transverse dynamics: $$\dot{\bx}_\perp =
f_\perp(\bx_\perp, \tau, \bu) \approx \pd{f_\perp}{\bx_\perp} \bx_\perp +
\pd{f_\perp}{\bu}(\bu - \bu_0(\tau)) = \bA_\perp(\tau)\bx_\perp +
\bB_\perp(\tau) \bar{\bu}.$$
Let's take a minute to appreciate the difference between this approach and time-varying LQR in the full coordinates. Of course, the behavior is quite different: time-varying LQR in the full coordinates will try to slow down or speed up to keep time with the nominal trajectory, where this controller makes no attempt to stabilize the phase variable. You might think you could design the original time-varying controller, $\bar\bu = \bK(t)\bar\bx,$ and just "project to the closest time" during execution (e.g. find the time $t = \argmin_\tau |\bx - \bx_0(\tau)|)$ and use the feedback corresponding to that time. But this projection is not guaranteed to be safe; you can find systems that are stabilizable by the transverse linearization are unstable in closed-loop using a feedback based on this projection.
Coming soon...
But there is an even more important reason to like the transverse LQR approach. If orbital stability is all you need, then this is a better formulation of the problem because you are asking for less. As we've just discussed with hybrid zero-dynamics, stabilizing $m$ degrees of freedom with $m$ actuators is potentially very different than stabilizing $m+1$ degrees of freedom. In the transverse formulation, we are asking LQR to minimize the cost only in the transverse coordinates (it is mathematically equivalent to designing a cost function in the full coordinates that is zero in the direction of the nominal trajectory). In practice, this can result is much smaller cost-to-go matrices, ${\bf S}(t)$, and smaller feedback gains, $\bK(t)$. For underactuated systems, this difference can be dramatic.
The observation that orbital stabilization of a trajectory can ask much less of your underactuated control system (and lead to smaller LQR feedback gains), is quite powerful. It is not limited to stabilizing periodic motions. If your aim is to stabilize a non-periodic path through state-space, but do not actually care about the timing, then formulating your stabilization can be a very good choice. You can find examples where a system is stabilizable in the transverse coordinates, but not in the full coordinates.
Coming soon...
Take care, though, as the converse can also be true: it's possible that a system could be stabilizable in the full coordinates but not in some transverse coordinates; if you choose those coordinates badly.
Consider a trajectory with $u(t) = 1$ (from any initial condition) for the double integrator. We can certainly stablize this trajectory in the full coordinates using LQR. Technically, one can choose transverse coordinates $\tau = \dot{q},$ and $x_\perp = q.$ Clearly $x_\perp$ is transverse to the nominal trajectory everywhere. But this transverse linearization is also clearly not stabilizable. It's a bad choice!
The general approach to designing the transverse coordinates
| Previous Chapter | Table of contents | Next Chapter |


AZLeafletComponentFactory
az.leaflet
This is purely a helper method to generate new Angular Directive Definition Objects for new azLeaflet directives that the user may want to create.
TODO: Document the onMapReady property of the DDO
AZLeafletComponentFactory(directive);
| Param | Type | Details |
|---|---|---|
| directive | Object |
|


Dear Dry,
Our National Young Feminist Leadership Conference Congressional Visit Day is a chance for activists from around the country to talk to their representatives about the issues that matter most to them. We’ll have a briefing with leaders in the morning, and then you will visit with your representatives and senators in the afternoon.
There’s only one way to get to Congressional Visit Day: *Register for the National Young Feminist Leadership Conference today! [ http://feministcampus.org/conferences/2015-nyflc/ ] *If you’ll be joining us for Congressional Visit Day, please also RSVP here. [ http://org.salsalabs.com/o/1400/p/salsa/event/common/public/?event_KEY=82726 ] [ http://org.salsalabs.com/o/1400/p/salsa/event/common/public/?event_KEY=82726 ]
Our conference gives folks the chance to tackle issues like LGBT rights, ending racism, women’s rights around the world, campus sexual assault, and more with their communities. And although registration for the conference is open until March 16, our special lodging prices end Friday, March 6. *To snag a spot at the conference and a room in the hotel, register today! [ http://feministcampus.org/conferences/2015-nyflc/ ]*
For more information about Congressional Visit Day, what to bring, what to expect, and more, visit the NYFLC portal! [ http://feministcampus.org/conferences/2015-nyflc/congressional-visit-day/ ] If you have any questions, please email us at<EMAIL_ADDRESS>[ mailto:nyflc@feminist.org?subject=Congressional%20Visit%20Day ].
See you on Capitol Hill!
For equality,
*The Feminist Campus Team*
“Alyssa, Edwith, duVergne, Nancy, and Taylor”
You have received this e-mail because of your interest in women’s issues. To unsubscribe, please click on the link below.


My Project
Main Page
Classes
Files
File List
File Members
src
transports
ws
ws Directory Reference
Directory dependency graph for ws:
Files
file
aws.c
file
aws.h
[code]
file
bws.c
file
bws.h
[code]
file
cws.c
file
cws.h
[code]
file
sha1.c
file
sha1.h
[code]
file
sws.c
file
sws.h
[code]
file
ws.c
file
ws.h
[code]
file
ws_handshake.c
file
ws_handshake.h
[code]
Generated by
1.8.11


|
M480 BSP V3.05.005
The Board Support Package for M480 Series
|
#include <ebi_reg.h>
Data Fields | |
| __IO uint32_t | CTL0 |
| __IO uint32_t | TCTL0 |
| __IO uint32_t | CTL1 |
| __IO uint32_t | TCTL1 |
| __IO uint32_t | CTL2 |
| __IO uint32_t | TCTL2 |
@addtogroup EBI External Bus Interface Controller(EBI) Memory Mapped Structure for EBI Controller
| EBI_T::CTL0 |
[0x0000] External Bus Interface Bank0 Control Register
| Bits | Field | Descriptions |
| [0] | EN | EBI Enable Bit
This bit is the functional enable bit for EBI. 0 = EBI function Disabled. 1 = EBI function Enabled. |
| [1] | DW16 | EBI Data Width 16-bit Select
This bit defines if the EBI data width is 8-bit or 16-bit. 0 = EBI data width is 8-bit. 1 = EBI data width is 16-bit. |
| [2] | CSPOLINV | Chip Select Pin Polar Inverse
This bit defines the active level of EBI chip select pin (EBI_nCS). 0 = Chip select pin (EBI_nCS) is active low. 1 = Chip select pin (EBI_nCS) is active high. |
| [3] | ADSEPEN | EBI Address/Data Bus Separating Mode Enable Bit
0 = Address/Data Bus Separating Mode Disabled. 1 = Address/Data Bus Separating Mode Enabled. |
| [4] | CACCESS | Continuous Data Access Mode
When con tenuous access mode enabled, the tASU, tALE and tLHD cycles are bypass for continuous data transfer request. 0 = Continuous data access mode Disabled. 1 = Continuous data access mode Enabled. |
| [10:8] | MCLKDIV | External Output Clock Divider
The frequency of EBI output clock (MCLK) is controlled by MCLKDIV as follow: 000 = HCLK/1. 001 = HCLK/2. 010 = HCLK/4. 011 = HCLK/8. 100 = HCLK/16. 101 = HCLK/32. 110 = HCLK/64. 111 = HCLK/128. |
| [18:16] | TALE | Extend Time of ALE
The EBI_ALE high pulse period (tALE) to latch the address can be controlled by TALE. tALE = (TALE+1)*EBI_MCLK. Note: This field only available in EBI_CTL0 register |
| [24] | WBUFEN | EBI Write Buffer Enable Bit
0 = EBI write buffer Disabled. 1 = EBI write buffer Enabled. Note: This bit only available in EBI_CTL0 register |
| EBI_T::CTL1 |
[0x0010] External Bus Interface Bank1 Control Register
| Bits | Field | Descriptions |
| [0] | EN | EBI Enable Bit
This bit is the functional enable bit for EBI. 0 = EBI function Disabled. 1 = EBI function Enabled. |
| [1] | DW16 | EBI Data Width 16-bit Select
This bit defines if the EBI data width is 8-bit or 16-bit. 0 = EBI data width is 8-bit. 1 = EBI data width is 16-bit. |
| [2] | CSPOLINV | Chip Select Pin Polar Inverse
This bit defines the active level of EBI chip select pin (EBI_nCS). 0 = Chip select pin (EBI_nCS) is active low. 1 = Chip select pin (EBI_nCS) is active high. |
| [3] | ADSEPEN | EBI Address/Data Bus Separating Mode Enable Bit
0 = Address/Data Bus Separating Mode Disabled. 1 = Address/Data Bus Separating Mode Enabled. |
| [4] | CACCESS | Continuous Data Access Mode
When con tenuous access mode enabled, the tASU, tALE and tLHD cycles are bypass for continuous data transfer request. 0 = Continuous data access mode Disabled. 1 = Continuous data access mode Enabled. |
| [10:8] | MCLKDIV | External Output Clock Divider
The frequency of EBI output clock (MCLK) is controlled by MCLKDIV as follow: 000 = HCLK/1. 001 = HCLK/2. 010 = HCLK/4. 011 = HCLK/8. 100 = HCLK/16. 101 = HCLK/32. 110 = HCLK/64. 111 = HCLK/128. |
| [18:16] | TALE | Extend Time of ALE
The EBI_ALE high pulse period (tALE) to latch the address can be controlled by TALE. tALE = (TALE+1)*EBI_MCLK. Note: This field only available in EBI_CTL0 register |
| [24] | WBUFEN | EBI Write Buffer Enable Bit
0 = EBI write buffer Disabled. 1 = EBI write buffer Enabled. Note: This bit only available in EBI_CTL0 register |
| EBI_T::CTL2 |
[0x0020] External Bus Interface Bank2 Control Register
| Bits | Field | Descriptions |
| [0] | EN | EBI Enable Bit
This bit is the functional enable bit for EBI. 0 = EBI function Disabled. 1 = EBI function Enabled. |
| [1] | DW16 | EBI Data Width 16-bit Select
This bit defines if the EBI data width is 8-bit or 16-bit. 0 = EBI data width is 8-bit. 1 = EBI data width is 16-bit. |
| [2] | CSPOLINV | Chip Select Pin Polar Inverse
This bit defines the active level of EBI chip select pin (EBI_nCS). 0 = Chip select pin (EBI_nCS) is active low. 1 = Chip select pin (EBI_nCS) is active high. |
| [3] | ADSEPEN | EBI Address/Data Bus Separating Mode Enable Bit
0 = Address/Data Bus Separating Mode Disabled. 1 = Address/Data Bus Separating Mode Enabled. |
| [4] | CACCESS | Continuous Data Access Mode
When con tenuous access mode enabled, the tASU, tALE and tLHD cycles are bypass for continuous data transfer request. 0 = Continuous data access mode Disabled. 1 = Continuous data access mode Enabled. |
| [10:8] | MCLKDIV | External Output Clock Divider
The frequency of EBI output clock (MCLK) is controlled by MCLKDIV as follow: 000 = HCLK/1. 001 = HCLK/2. 010 = HCLK/4. 011 = HCLK/8. 100 = HCLK/16. 101 = HCLK/32. 110 = HCLK/64. 111 = HCLK/128. |
| [18:16] | TALE | Extend Time of ALE
The EBI_ALE high pulse period (tALE) to latch the address can be controlled by TALE. tALE = (TALE+1)*EBI_MCLK. Note: This field only available in EBI_CTL0 register |
| [24] | WBUFEN | EBI Write Buffer Enable Bit
0 = EBI write buffer Disabled. 1 = EBI write buffer Enabled. Note: This bit only available in EBI_CTL0 register |
| EBI_T::TCTL0 |
[0x0004] External Bus Interface Bank0 Timing Control Register
| Bits | Field | Descriptions |
| [7:3] | TACC | EBI Data Access Time
TACC define data access time (tACC). tACC = (TACC +1) * EBI_MCLK. |
| [10:8] | TAHD | EBI Data Access Hold Time
TAHD define data access hold time (tAHD). tAHD = (TAHD +1) * EBI_MCLK. |
| [15:12] | W2X | Idle Cycle After Write
This field defines the number of W2X idle cycle. W2X idle cycle = (W2X * EBI_MCLK). When write action is finish, W2X idle cycle is inserted and EBI_nCS return to idle state. |
| [22] | RAHDOFF | Access Hold Time Disable Control When Read
0 = The Data Access Hold Time (tAHD) during EBI reading is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI reading is Disabled. |
| [23] | WAHDOFF | Access Hold Time Disable Control When Write
0 = The Data Access Hold Time (tAHD) during EBI writing is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI writing is Disabled. |
| [27:24] | R2R | Idle Cycle Between Read-to-read
This field defines the number of R2R idle cycle. R2R idle cycle = (R2R * EBI_MCLK). When read action is finish and next action is going to read, R2R idle cycle is inserted and EBI_nCS return to idle state. |
| EBI_T::TCTL1 |
[0x0014] External Bus Interface Bank1 Timing Control Register
| Bits | Field | Descriptions |
| [7:3] | TACC | EBI Data Access Time
TACC define data access time (tACC). tACC = (TACC +1) * EBI_MCLK. |
| [10:8] | TAHD | EBI Data Access Hold Time
TAHD define data access hold time (tAHD). tAHD = (TAHD +1) * EBI_MCLK. |
| [15:12] | W2X | Idle Cycle After Write
This field defines the number of W2X idle cycle. W2X idle cycle = (W2X * EBI_MCLK). When write action is finish, W2X idle cycle is inserted and EBI_nCS return to idle state. |
| [22] | RAHDOFF | Access Hold Time Disable Control When Read
0 = The Data Access Hold Time (tAHD) during EBI reading is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI reading is Disabled. |
| [23] | WAHDOFF | Access Hold Time Disable Control When Write
0 = The Data Access Hold Time (tAHD) during EBI writing is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI writing is Disabled. |
| [27:24] | R2R | Idle Cycle Between Read-to-read
This field defines the number of R2R idle cycle. R2R idle cycle = (R2R * EBI_MCLK). When read action is finish and next action is going to read, R2R idle cycle is inserted and EBI_nCS return to idle state. |
| EBI_T::TCTL2 |
[0x0024] External Bus Interface Bank2 Timing Control Register
| Bits | Field | Descriptions |
| [7:3] | TACC | EBI Data Access Time
TACC define data access time (tACC). tACC = (TACC +1) * EBI_MCLK. |
| [10:8] | TAHD | EBI Data Access Hold Time
TAHD define data access hold time (tAHD). tAHD = (TAHD +1) * EBI_MCLK. |
| [15:12] | W2X | Idle Cycle After Write
This field defines the number of W2X idle cycle. W2X idle cycle = (W2X * EBI_MCLK). When write action is finish, W2X idle cycle is inserted and EBI_nCS return to idle state. |
| [22] | RAHDOFF | Access Hold Time Disable Control When Read
0 = The Data Access Hold Time (tAHD) during EBI reading is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI reading is Disabled. |
| [23] | WAHDOFF | Access Hold Time Disable Control When Write
0 = The Data Access Hold Time (tAHD) during EBI writing is Enabled. 1 = The Data Access Hold Time (tAHD) during EBI writing is Disabled. |
| [27:24] | R2R | Idle Cycle Between Read-to-read
This field defines the number of R2R idle cycle. R2R idle cycle = (R2R * EBI_MCLK). When read action is finish and next action is going to read, R2R idle cycle is inserted and EBI_nCS return to idle state. |


A Custom Tile Source can be create via inline configuration by specifying a single function named 'getTileUrl', along with the required values for 'height', 'width'. Optional values include 'tileSize', 'tileOverlap', 'minLevel', and 'maxLevel'. Additionally, any default functions implemented by OpenSeadragon.TileSource can be overridden. Functionally this allows you to define a new TileSource implementation inline.
Alternatively, you can always create a new tile source which implements the required interfaces 'getTileUrl', 'configure', and 'supports'.
Minimally, an inline configuration for a custom tile source only needs to implement the 'getTileUrl' interface and provide a height and width for the maximum resolution of the image.
Below is a minimal inline configuration which pull tiles from a NASA Blue Marble tile set transformed into tiles hosted on Amazon S3 ( compliments of Michal Migurski - see http://mike.teczno.com/notes/blue-marble-tiles.html ). Note that the default tileSize is available as a property of the tile source.
OpenSeadragon({ id: "example-custom-tilesource", prefixUrl: "/openseadragon", navigatorSizeRatio: 0.25, wrapHorizontal: true, tileSources: { height: 512*256, width: 512*256, tileSize: 256, minLevel: 8, getTileUrl: function( level, x, y ){ return "http://s3.amazonaws.com/com.modestmaps.bluemarble/"+(level-8)+"-r"+x+"-c"+y+".jpg"; } } });
Here is another inline example which makes use of a tile set created by Aaron Straup Cope ( see http://shapetiles.spum.org/about/ ) which provide a visualization of geotagged Flikr photos. Note in this case we set blendTime to zero since png with alpha channel (transparency) can look unusual during blending.
OpenSeadragon({ ... showNavigator: false, blendTime: 0, wrapHorizontal: true, tileSources: { height: 1024*256, width: 1024*256, tileSize: 256, minLevel: 9, getTileUrl: function( level, x, y ){ function zeropad( i ) { var n = String( i ), m = 6 - n.length; n = (m < 1) ? n : new Array(m + 1).join( "0" ) + n; return n.substr(0, 3) + "/" + n.substr(3); }; return "http://s3.amazonaws.com/info.aaronland.tiles.shapetiles/"+(level-8)+"/"+zeropad(x)+"/"+zeropad(y)+".png"; } } ... });


DARSY is an intelligent personal assistant, human language interface and automation software for Windows PC that allows you to interact with your computer using voice commands in English language. DARSY makes it possible for you to control your computer using natural language commands and makes your life easier. DARSY is not like Siri or Cortana for PC but rather a powerful personal and office productivity software.
It isn't just like a chat-bot, its priority is to be super functional and to help you in doing tasks. You can either type commands or speak to it and DARSY will understand what you want to do. Moreover, using speech recognition built in DARSY for WebApp you can interact with your computer from anywhere in your house over a Wi-Fi network.